DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2019.44

Online Disjoint Set Cover Without Prior Knowledge

Authors: Yuval Emek, Adam Goldbraikh, and Erez Kantor

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ESA.2019.44,
  author =	{Emek, Yuval and Goldbraikh, Adam and Kantor, Erez},
  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 =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.44},
  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}
}

Search Results

Documents authored by Goldbraikh, Adam

Online Disjoint Set Cover Without Prior Knowledge

Abstract

Cite as

Thanks for your feedback!

Could not send message