Document Open Access Logo

Online Set Cover with Set Requests

Authors Kshipra Bhawalkar, Sreenivas Gollapudi, Debmalya Panigrahi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.64.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Kshipra Bhawalkar
Sreenivas Gollapudi
Debmalya Panigrahi

Cite As Get BibTex

Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi. Online Set Cover with Set Requests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 64-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.64

Abstract

We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well.

Subject Classification

Keywords
  • Online Algorithms
  • Set Cover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Susanne Albers. Online algorithms: a survey. Math. Program., 97(1-2):3-26, 2003. Google Scholar
  2. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-370, 2009. Google Scholar
  3. James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM, 44(3):486-504, 1997. Google Scholar
  4. Yossi Azar. On-line load balancing. In Online Algorithms, pages 178-195, 1996. Google Scholar
  5. Yossi Azar, Umang Bhaskar, Lisa K. Fleischer, and Debmalya Panigrahi. Online mixed packing and covering. In SODA, 2013. Google Scholar
  6. Yossi Azar, Joseph Naor, and Raphael Rom. The competitiveness of on-line assignments. J. Algorithms, 18(2):221-237, 1995. Google Scholar
  7. M. Balazinska, B. Howe, and D. Suciu. Data markets in the cloud: An opportunity for the database community. PVLDB, 4(12):1482-1485, 2011. Google Scholar
  8. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA, 1998. Google Scholar
  9. Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  10. Anupam Gupta and Viswanath Nagarajan. Approximating sparse covering integer programs online. In ICALP (1), pages 436-448, 2012. Google Scholar
  11. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274-296, 2001. Google Scholar
  12. Simon Korman. On the use of randomization in the online set cover problem. M.S. thesis, Weizmann Institute of Science, 2005. Google Scholar
  13. Paraschos Koutris, Prasang Upadhyaya, Magdalena Balazinska, Bill Howe, and Dan Suciu. Querymarket demonstration: Pricing for online data markets. PVLDB, 5(12):1962-1965, 2012. Google Scholar
  14. Chao Li and Gerome Miklau. Pricing aggregate queries in a data marketplace. In WebDB, pages 19-24, 2012. Google Scholar
  15. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1997. Google Scholar
  16. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact