论文标题
用于覆盖，包装和最大加权匹配的分布式算法
Distributed algorithms for covering, packing and maximum weighted matching
论文作者
论文摘要
本文提供了多结合式的，分布式的D-Approximation算法，用于涵盖子模成本和单调覆盖约束的问题（覆盖下）。近似值d是任何约束中的最大变量数。特殊情况包括涵盖混合整数线性程序（CMIP）和加权顶点盖（d = 2）。通过二元性，本文还提供了分数包装线性程序（其中d是发生任何变量的最大约束数量）的poly-logarithmic-round，分布式的D-AppRoximation算法，对于最大加权C型的最大约束数量（其中D是Hypereded of Hypereded of Hypereded;对于图形d = 2 = 2 = 2）。该论文还提供了CMIP的平行（RNC）2-辅助算法，每个约束和加权顶点盖有两个变量。算法是随机的。所有近似值比完全匹配了可比集中算法的近似值。
This paper gives poly-logarithmic-round, distributed D-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio D is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with D=2). Via duality, the paper also gives poly-logarithmic-round, distributed D-approximation algorithms for Fractional Packing linear programs (where D is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where D is the maximum size of any of the hyperedges; for graphs D=2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.
