Admission control to minimize rejections and online set cover with repetitions
By Noga Alon, Yossi Azar, Shai Gutner. ACM Symposium on Parallelism in Algorithms and Architectures, 2005
488 citations recorded by the source corpus.
We study the admission control problem in general networks.Communication requests arrive over time, and the online algorithmaccepts or rejects each request while maintaining the capacitylimitations of the network. The admission control problem has beenusually analyzed as a benefit problem, where the goal is to devisean online algorithm that accepts the maximum number of requestspossible. The problem with this objective function is that evenalgorithms with optimal competitive ratios may reject almost all ofthe requests, when it would have been possible to reject only afew. This could be inappropriate for settings in which rejectionsare intended to be rare events. In this paper, we consider preemptive online algorithms whosegoal is to minimize the number of rejected requests. Each requestarrives together with the path it should be routed on. We show an<i>O</i>(log<sup>2</sup>(<i>m</i><i>c</i>))-competitiverandomized algorithm for the weighted case, where<i>m</i> is the number of edges in the graph and<i>c</i> is the maximum edge capacity. For theunweighted case, we give an <i>O</i>(log<i>m</i> log <i>c</i>)-competitiverandomized algorithm. This settles an open question of Blum, Kalaiand Kleinberg raised in [10]. We note that allowing preemption andhandling requests with given paths are essential for avoidingtrivial lower bounds. The admission control problem is a generalization of the onlineset cover with repetitions problem, whose input is a family of<i>m</i> subsets of a ground set of<i>n</i> elements. Elements of the ground set are givento the online algorithm one by one, possibly requesting eachelement a multiple number of times. (If each element arrives atmost once, this corresponds to the online set cover problem.) Thealgorithm must cover each element by different subsets, accordingto the number of times it has been requested. We give an <i>O</i>(log <i>m</i> log<i>n</i>)-competitive randomized algorithm for theonline set cover with repetitions problem. This matches a recentlower bound of Ω(log <i>m</i> log<i>n</i>) given by Feige and Korman for the competitiveratio of any randomized <i>polynomial</i> timealgorithm, under the <i>BPP</i> ≠<i>NP</i> assumption. Given any constant ε >0, an <i>O</i>(log <i>m</i>log<i>n</i>)-competitive deterministic bicriteriaalgorithm is shown that covers each element by at least(1-ε)<i>k</i> sets, where <i>k</i>is the number of times the element is covered by the optimalsolution.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/1b350be47546b008b31e68155440fae98fc27861
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Niv Buchbinder
- Zaher A. A. Hallab
- Kyungmi Kim
- J. N. Kim
- Joseph (Seffi) Naor
- B. Taskar
- Alex Kulesza
- Moran Feldman
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- The Design of Competitive Online Algorithms via a Primal-Dual Approach (2009, background): “Such problems are, for example, the admission control problem [5], the parking permit problem [83] and the inventory problem [31].”
- The Moderating Effect of Travel Experience in a Destination on the Relationship Between the Destination Image and the Intention to Revisit (2012, background): “Census Bureau report, in 2008 there were 3,151,000 high school completers in the United States (in comparison to 1,679,000 in 1960); 69% of them enrolled in college (in comparison to 45.1% in 1960). There are various factors that have contributed to an increase in youthstudent travel; some of the fa”