Weighted Matchings via Unweighted Augmentations

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively parallel computation (MPC) model and in the streaming model.
For the MPC and the multi-pass streaming model, we show that any algorithm computing a (1- delta)-approximate unweighted matching in bipartite graphs can be translated into an algorithm that computes a (1 - epsilon(delta))-approximate maximum weighted matching. Furthermore, this translation incurs only a constant factor (that depends on epsilon > 0) overhead in the complexity. Instantiating this with the current best MPC algorithm for unweighted matching yields a (1 - epsilon)-approximation algorithm for maximum weighted matching that uses O-epsilon (log logn) rounds, O(m/n) machines per round, and Oe (n poly(logn)) memory per machine. This improves upon the previous best approximation guarantee of (1/2 - epsilon) for weighted graphs. In the context of single-pass streaming with random edge arrivals, our techniques yield a (1/2 + c)-approximation algorithm thus breaking the natural barrier of 1/2.


Published in:
Proceedings Of The 2019 Acm Symposium On Principles Of Distributed Computing (Podc '19), 491-500
Presented at:
38th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, CANADA, Jul 29-Aug 02, 2019
Year:
Jan 01 2019
Publisher:
New York, ASSOC COMPUTING MACHINERY
ISBN:
978-1-4503-6217-7
Keywords:




 Record created 2020-10-02, last modified 2020-10-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)