Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality

摘要

We present efficient distributed δ-approximation algorithms for FRACTIONAL PACKING and MAXIMUM WEIGHTED b-MATCHING in hy-pergraphs, 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(log~2 m) rounds in expectation and with high probability.