Cited By
View all- Markarian CMeyer auf der Heide FGeorgiou CSpirakis P(2015)Online Resource LeasingProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767454(343-344)Online publication date: 21-Jul-2015
Randomized Online Algorithms for Set Cover Leasing Problems
Pages 25 - 34
Abstract
In the leasing variant of Set Cover presented by Anthony et al. [1], elements arrive over time and must be covered by sets from a family of subsets of . Each set can be leased for different periods of time. Let and . Leasing a set for a period incurs a cost and allows to cover its elements for the next time steps. The objective is to minimize the total cost of the sets leased, such that elements arriving at any time are covered by sets which contain them and are leased during time . Anthony et al. [1] gave an optimal -approximation for the problem in the offline setting, unless [22]. In this paper, we give randomized algorithms for variants of Set Cover Leasing in the online setting, including a generalization of Online Set Cover with Repetitions presented by Alon et al. [2], where elements appear multiple times and must be covered by a different set at each arrival. Our results improve the competitive factor of Online Set Cover with Repetitions [2] to, where is the maximum number of sets an element belongs to.
References
[1]
Anthony BM and Gupta A Fischetti M and Williamson DP Infrastructure leasing problems Integer Programming and Combinatorial Optimization 2007 Heidelberg Springer 424-438
[2]
Alon, N., Azar, Y., Gutner, S.: Admission control to minimize rejections and online set cover with repetitions. In: 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Prague, pp. 238–244 (2005)
[3]
Berman P and DasGubta B Approximating the online set multicover problems via randomized winnowing Theor. Comput. Sci. 2008 393 13 54-71
[4]
Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N.: A general approach to online network optimization problems. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, pp. 577–586 (2004)
[5]
Kling P, Meyer auf der Heide F, and Pietrzyk P Even G and Halldórsson MM An algorithm for online facility leasing Structural Information and Communication Complexity 2012 Heidelberg Springer 61-72
[6]
Nagarajan C and Williamson DP Lodi A, Panconesi A, and Rinaldi G Offline and online facility leasing Integer Programming and Combinatorial Optimization 2008 Heidelberg Springer 303-315
[7]
Chavatal V A greedy heuristic for the set-covering problem Math. Oper. Res. 1979 4 3 233-235
[8]
Feige U A threshold of ln n for approximating set cover J. ACM 1998 45 4 634-652
[9]
Feige, U., Korman, S.: Personal communication
[10]
Johnson DS Approximation algorithms for combinatorial problems J. Comput. Syst. Sci. 1974 9 256-278
[11]
Lovasz L On the ratio of optimal and fractional covers Discrete Math. 1975 13 383-390
[12]
Berman P, DasGupta B, and Sontag E Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks Discrete Appl. Math. 2007 155 67 733-749
[13]
Vazirani, V.: Approximation Algorithms (2001)
[14]
Fotakis D A primal-dual algorithm for online non-uniform facility location J. Discrete Algorithms 2007 5 141-148
[15]
Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. In: 35th Annual ACM Symposium on the Theory of Computation (STOC), San Diego, CA, USA, pp. 100–105 (2003)
[16]
Awerbuch, B., Azar, Y., Fiat, A., Leighton, T.: Making commitments in the face of uncertainty: how to pick a winner almost every time. In: 28th Annual ACM Symposium on Theory of Computing (STOC), Pennsylvania, USA, pp. 519–530 (1996)
[17]
Meyerson, A.: Online facility location. In: 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, Nevada, USA, pp. 426–431 (2001)
[18]
Fotakis D Baeten JCM, Lenstra JK, Parrow J, and Woeginger GJ On the competitive ratio for online facility location Automata, Languages and Programming 2003 Heidelberg Springer 637-652
[19]
Buchbinder N and Naor JS Brodal GS and Leonardi S Online primal-dual algorithms for covering and packing problems Algorithms – ESA 2005 2005 Heidelberg Springer 689-701
[20]
Meyerson, A.: The parking permit problem. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, USA, pp. 274–284 (2005)
[21]
Malik, S., Huet, F.: Virtual cloud: rent out the rented resources. In: 6th IEEE International Conference for Internet Technology and Secured Transactions (ICITST), Abu Dhabi, UAE, pp. 536–541 (2011)
[22]
Alon N, Moshkovitz D, and Safra S Algorithmic construction of sets for k-restrictions ACM Trans. Algorithms 2006 2 153-177
Index Terms
- Randomized Online Algorithms for Set Cover Leasing Problems
Index terms have been assigned to the content through auto-classification.
Recommendations
Approximating the online set multicover problems via randomized winnowing
In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every S@?S, and a ''coverage factor'' (positive integer) k. A subset {i"0,...
The Online Set Cover Problem
Let $X=\{1,2,\ldots,n\}$ be a ground set of $n$ elements, and let ${\cal S}$ be a family of subsets of $X$, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. Consider the following online version of the set cover problem, ...
Online and dynamic algorithms for set cover
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingIn this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2014
752 pages
© Springer International Publishing Switzerland 2014.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 19 December 2014
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View all- Markarian CMeyer auf der Heide FGeorgiou CSpirakis P(2015)Online Resource LeasingProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767454(343-344)Online publication date: 21-Jul-2015
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in