neal young / Koufogiannakis09DistributedPacking
We present efficient distributed δ-approximation algorithms for fractional packing and maximum weighted b-matching in hypergraphs, where δ is the maximum number of packing constraints in which a variable appears (for maximum weighted b-matching δ is the maximum edge degree - for graphs δ = 2). (a) For δ = 2 the algorithm runs in O(log m) rounds in expectation and with high probability. (b) For general δ, the algorithm runs in O(log2 m) rounds in expectation and with high probability.
(This paper gives distributed algorithms for the duals of problems considered in Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost .)Conference version of part of Distributed Algorithms for Covering, Packing and Maximum Weighted Matching.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.