Improved Local Computation Algorithm for Set Cover via Sparsification
Improved Local Computation Algorithm for Set Cover via Sparsification
复制标题
通过稀疏化改进集覆盖的局部计算算法
DOI：
10.1137/1.9781611975994.181
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vakilian, A.
中科院分区：
文献类型：
--
作者：
Grunau, C.;Mitrovic, S.;Rubinfeld, R.;Vakilian, A.
我们为集合覆盖问题设计了局部计算算法（LCA）。给定一个集合系统，其中每个集合的大小最多，并且每个元素最多包含在 t 个集合中，该算法报告给定集合是否在某个固定集合覆盖中，其预期大小为 O(logs) 乘以最小分数集合覆盖值。我们的算法需要sO(logs)tO(logs+log logt))查询。该结果改进了在 [Kuhn 等人，SODA’06] 的结果上应用 [Parnas 和 Ron，TCS’07] 的约简，导致查询复杂度为 (st)O(log s · logt)。为了获得此结果，我们设计了一种并行集覆盖算法，该算法允许使用 [Ghaffari 和 Uitto, SODA’19] 中引入的 asparsification 技术在 LCA 模型中对最大独立集进行有效模拟问题。并行算法以类似于 [Berger 等人，FOCS’89] 的 PRAM 算法的方式将集合的随机子集添加到解决方案中。然而，我们的算法的不同之处在于它从不撤销其决策，这导致自适应轮数较少。这需要一种可能具有独立意义的新颖的近似分析。
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at mostsand each element is contained in at mosttsets, the algorithm reports whether a given set is in some fixed set cover whose expected size isO(logs) times the minimum fractional set cover value. Our algorithm requiressO(logs)tO(logs+log logt))queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS’07] on the result of [Kuhn et al., SODA’06], which leads to a query complexity of (st)O(log s · logt).To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using asparsificationtechnique introduced in [Ghaffari and Uitto, SODA’19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al., FOCS’89]. However, our algorithm differs in the way that it neverrevokesits decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.
登录
查看更多内容
集合覆盖问题的单遍流复杂性的严格界限
DOI：
--
发表时间：
2016
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Sepehr Assadi;S. Khanna;Yang Li
通讯作者：
Yang Li
DOI：
10.1145/3087556.3087585
发表时间：
2016
期刊：
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
M. Bateni;Hossein Esfandiari;V. Mirrokni
通讯作者：
V. Mirrokni
流媒体集覆盖问题的严格界限
DOI：
10.1145/2902251.2902287
发表时间：
2015
期刊：
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
--
作者：
P. Indyk;S. Mahabadi;A. Vakilian
通讯作者：
A. Vakilian
关于布景覆盖问题的流式传输和通信复杂性
影响因子：
0.9
作者：
E. Demaine;P. Indyk;S. Mahabadi;A. Vakilian
通讯作者：
A. Vakilian
流模型中的分数集覆盖
DOI：
--
发表时间：
2017
期刊：
20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problem (APPROX 2017
影响因子：
--
作者：
Indyk, P.;Mahabadi, S.;Rubinfeld, R.;Ullman, J.;Vakilian, A.;Yodpinyanee, A.
通讯作者：
Yodpinyanee, A.