文章基本信息

标题：Fractional Set Cover in the Streaming Model
本地全文：下载
作者：Piotr Indyk ; Sepideh Mahabadi ; Ronitt Rubinfeld 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：12:1-12:20
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the Fractional Set Cover problem in the streaming model. That is, we consider the relaxation of the set cover problem over a universe of n elements and a collection of m sets, where each set can be picked fractionally, with a value in [0,1]. We present a randomized (1+a)-approximation algorithm that makes p passes over the data, and uses O(polylog(m,n,1/a) (mn^(O(1/(pa)))+n)) memory space. The algorithm works in both the set arrival and the edge arrival models. To the best of our knowledge, this is the first streaming result for the fractional set cover problem. We obtain our results by employing the multiplicative weights update framework in the streaming settings.
关键词：Streaming Algorithms; Fractional Set Cover; LP relaxation; Multiplicative Weight Update