Admission control to minimize rejections and online set cover with repetitions
Noga Alon, Yossi Azar, Shai Gutner · 2005
Abstract We study the admission control problem in general networks. Communication requests arrive overtime, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem has been usually analyzed as a benefit problem, where thegoal is to devise an online algorithm that accepts the maximum number of requests possible. The problem with this objective function is that even algorithms with optimal competitive ratios may reject almost allof the requests, when it would have been possible to reject only a few. This could be inappropriate for settings in which rejections are intended to be rare events.In this paper, we consider preemptive online algorithms whose goal is to minimize the number of rejected requests. Each request arrives together with the path it should be routed on. We show an O(log2(mc))-competitive randomized algorithm for the weighted case, where m is the number of edgesin the graph and c is the maximum edge capacity. For the unweighted case, we give an O(log m log c)-competitive randomized algorithm. This settles an open question of Blum, Kalai and Kleinberg raised in [10]. We note that allowing preemption and handling requests with given paths are essential for avoidingtrivial lower bounds. The admission control problem is a generalization of the online set cover with repetitions problem,whose input is a family of m subsets of a ground set of n elements. Elements of the ground set are givento the online algorithm one by one, possibly requesting each element a multiple number of times. (If each element arrives at most once, this corresponds to the online set cover problem.) The algorithm must covereach element by different subsets, according to the number of times it has been requested. We give an O(log m log n)-competitive randomized algorithm for the the online set cover with rep-etitions problem. This matches a recent lower bound of \\Omega (log m log n) given by Feige and Korman forthe competitive ratio of any randomized polynomial time algorithm, under the BP P 6 = N P assumption.Given any constant ffl> 0, we show an O(log m log n)-competitive deterministic bicriteria algorithm thatcovers each element by at least (1-