Greedy and Local Ratio Algorithms in the MapReduce Model
Greedy and Local Ratio Algorithms in the MapReduce Model
复制标题
MapReduce 模型中的贪心算法和局部比率算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Paul Liu
中科院分区：
文献类型：
--
作者：
Nicholas J. A. Harvey;Christopher Liaw;Paul Liu
MapReduce已成为设计分布式算法以在集群上处理大数据的事实上的标准模型。针对聚类、图优化和子模优化问题设计高效的MapReduce算法，已有大量研究。在此背景下，我们开发了用于设计贪心算法和局部比率算法的新技术。我们的随机局部比率技术在加权顶点覆盖和加权匹配问题上可给出2近似解，在加权集合覆盖问题上可给出f近似解，且所有这些都只需常数轮次的MapReduce操作。我们的随机贪心技术为最大独立集、最大团问题提供了算法，在加权集合覆盖问题上给出了(1 + ε)1n Δ近似解。我们还给出了用于顶点着色的贪心算法，可使用(1 + o(1))Δ种颜色，以及用于边着色的贪心算法，可使用(1 + o(1))Δ种颜色。
MapReduce has become the de facto standard model for designing distributed algorithms to process big data on a cluster. There has been considerable research on designing efficient MapReduce algorithms for clustering, graph optimization, and submodular optimization problems. We develop new techniques for designing greedy and local ratio algorithms in this setting. Our randomized local ratio technique gives $2$-approximations for weighted vertex cover and weighted matching, and an f -approximation for weighted set cover, all in a constant number of MapReduce rounds. Our randomized greedy technique gives algorithms for maximal independent set, maximal clique, and a (1+ε)1n Δ-approximation for weighted set cover. We also give greedy algorithms for vertex colouring with $(1+o(1))Δ colours and edge colouring with (1+o(1))Δ colours.
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai