License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.44
URN: urn:nbn:de:0030-drops-111654
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11165/
Go to the corresponding LIPIcs Volume Portal

Emek, Yuval ; Goldbraikh, Adam ; Kantor, Erez

Online Disjoint Set Cover Without Prior Knowledge

pdf-format:
LIPIcs-ESA-2019-44.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{emek_et_al:LIPIcs:2019:11165,
  author =	{Yuval Emek and Adam Goldbraikh and Erez Kantor},
  title =	{{Online Disjoint Set Cover Without Prior Knowledge}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{44:1--44:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11165},
  URN =		{urn:nbn:de:0030-drops-111654},
  doi =		{10.4230/LIPIcs.ESA.2019.44},
  annote =	{Keywords: disjoint set cover, online algorithms, competitive analysis, competitiveness with high probability}
}

Keywords: disjoint set cover, online algorithms, competitive analysis, competitiveness with high probability
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI