文章基本信息

标题：Online Disjoint Set Cover Without Prior Knowledge
本地全文：下载
作者：Yuval Emek ; Adam Goldbraikh ; Erez Kantor 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：144
页码：1-16
DOI：10.4230/LIPIcs.ESA.2019.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：disjoint set cover; online algorithms; competitive analysis; competitiveness with high probability