Algorithmics and Complexity of All-or-Nothing Resource Allocation with Delay Constraints
International Journal of Foundations of Computer Science · 23.05.2026 · 1-25
DOI: 10.1142/s0129054126490079 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 23.05.2026. Verfasst von Meiyun Lu und 2 weiteren Autor:innen. Gefördert von: National Natural Science Foundation of China, Key Project of Natural Science Foundation of Fujian Province, Guangzhou Leading Science and Technology Talent Program.
Abstract (Originalsprache)
In the paper, we study the All-or-Nothing Resource Allocation problem with Delay Constraints (AoNRA-DC). We are given a set of servers and a set of clients, where each server has a resource supply and each client has a demand for resource. The objective is to maximize the number of clients whose demands are fully satisfied by servers within the delay constraint. Importantly, if a client’s demand is not completely satisfied, the client is considered unserved. Moreover, clients may be served by multiple servers, and servers may serve multiple clients simultaneously. By reducing to the maximum set packing problem, we show that AoNRA-DC is NP-hard and cannot be approximated within any constant factor. Next, observing that in many practical scenarios the delay function satisfies the metric property (i.e., the triangle inequality), we present an approximation algorithm with a bifactor ratio of [Formula: see text] based on linear programming rounding. That means, our approach guarantees that the solution serves at least one-third as many clients as the optimal solution while ensuring that the delay remains within five times the predefined threshold.
Förderung
- National Natural Science Foundation of China
- Key Project of Natural Science Foundation of Fujian Province
- Guangzhou Leading Science and Technology Talent Program
Zitieren
APA
Lu, M., Guo, L., & Fang, W. (2026). Algorithmics and Complexity of All-or-Nothing Resource Allocation with Delay Constraints. International Journal of Foundations of Computer Science, 1-25. https://doi.org/10.1142/s0129054126490079
Vancouver
Lu M, Guo L, Fang W. Algorithmics and Complexity of All-or-Nothing Resource Allocation with Delay Constraints. International Journal of Foundations of Computer Science. 2026:1-25. doi:10.1142/s0129054126490079
BibTeX
@article{Lu2026,
author = {Lu, Meiyun and Guo, Longkun and Fang, Weijie},
title = {Algorithmics and Complexity of All-or-Nothing Resource Allocation with Delay Constraints},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--25},
doi = {10.1142/s0129054126490079}
}
EUVIMED