Online Disjoint Set Cover Without Prior Knowledge

Authors Yuval Emek, Adam Goldbraikh, Erez Kantor



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.44.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Yuval Emek
  • Technion, Haifa, Israel
Adam Goldbraikh
  • Technion, Haifa, Israel
Erez Kantor
  • Akamai, Cambridge, Massachusetts, USA

Cite AsGet BibTex

Yuval Emek, Adam Goldbraikh, and Erez Kantor. Online Disjoint Set Cover Without Prior Knowledge. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.44

Abstract

The disjoint set cover (DSC) problem is a fundamental combinatorial optimization problem concerned with partitioning the (hyper)edges of a hypergraph into (pairwise disjoint) clusters so that the number of clusters that cover all nodes is maximized. In its online version, the edges arrive one-by-one and should be assigned to clusters in an irrevocable fashion without knowing the future edges. This paper investigates the competitiveness of online DSC algorithms. Specifically, we develop the first (randomized) online DSC algorithm that guarantees a poly-logarithmic (O(log^{2} n)) competitive ratio without prior knowledge of the hypergraph’s minimum degree. On the negative side, we prove that the competitive ratio of any randomized online DSC algorithm must be at least Omega((log n)/(log log n)) (even if the online algorithm does know the minimum degree in advance), thus establishing the first lower bound on the competitive ratio of randomized online DSC algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • disjoint set cover
  • online algorithms
  • competitive analysis
  • competitiveness with high probability

Metrics

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

References

  1. 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
  2. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016. Google Scholar
  3. Anne Auger and Benjamin Doerr. Theory of randomized search heuristics: Foundations and recent developments, volume 1, chapter 1: Analyzing Randomized Search Heuristics: Tools from Probability Theory, pages 1-20. World Scientific, 2011. Google Scholar
  4. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  5. 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
  6. Yuval Emek and Adi Rosén. Semi-Streaming Set Cover. ACM Trans. Algorithms, 13(1):6:1-6:22, 2016. Google Scholar
  7. Sudipto Guha, Andrew McGregor, and David Tench. Vertex and Hyperedge Connectivity in Dynamic Graph Streams. In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '15, pages 241-247, 2015. Google Scholar
  8. Dmitry Kogan and Robert Krauthgamer. Sketching Cuts in Graphs and Hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15, pages 367-376, 2015. Google Scholar
  9. Ashwin Pananjady, Vivek Kumar Bagaria, and Rahul Vaze. The online disjoint set cover problem and its applications. In Computer Communications (INFOCOM), 2015 IEEE Conference on, pages 1221-1229. IEEE, 2015. Google Scholar
  10. Ashwin Pananjady, Vivek Kumar Bagaria, and Rahul Vaze. Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks. IEEE/ACM Transactions on Networking, 25(1):98-111, 2017. Google Scholar
  11. Alessandro Panconesi and Aravind Srinivasan. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds. SIAM J. Comput., 26(2):350-368, 1997. Google Scholar
  12. Barna Saha and Lise Getoor. On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch. In Proceedings of the SIAM International Conference on Data Mining SDM, pages 697-708, 2009. 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