LIPIcs.ESA.2019.44.pdf
- Filesize: 0.51 MB
- 16 pages
Document
Online Disjoint Set Cover Without Prior Knowledge
Authors
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
Cite As Get 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)
0PDF Downloads
References
-
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The Online Set Cover Problem. SIAM J. Comput., 39(2):361-370, 2009.
-
Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016.
-
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.
-
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.
-
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.
-
Yuval Emek and Adi Rosén. Semi-Streaming Set Cover. ACM Trans. Algorithms, 13(1):6:1-6:22, 2016.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.