Algorithmics and Complexity of All-or-Nothing Resource Allocation with Delay Constraints

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.