Weighted Matchings via Unweighted Augmentations
share
We design a generic method for reducing 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 streaming model and in the massively parallel computation (MPC) model. In the context of streaming with random edge arrivals, our techniques yield a (1/2+c)-approximation algorithm thus breaking the natural barrier of 1/2. For multi-pass streaming and the MPC model, we show that any algorithm computing a (1-δ)-approximate unweighted matching in bipartite graphs can be translated into an algorithm that computes a (1-ε(δ))-approximate maximum weighted matching. Furthermore, this translation incurs only a constant factor (that depends on ε> 0) overhead in the complexity. Instantiating this with the current best multi-pass streaming and MPC algorithms for unweighted matchings yields the following results for maximum weighted matchings: * A (1-ε)-approximation streaming algorithm that uses O_ε(1) passes and O_ε(n poly ( n)) memory. This is the first (1-ε)-approximation streaming algorithm for weighted matchings that uses a constant number of passes (only depending on ε). * A (1 - ε)-approximation algorithm in the MPC model that uses O_ε( n) rounds, O(m/n) machines per round, and O_ε(n poly( n)) memory per machine. This improves upon the previous best approximation guarantee of (1/2-ε) for weighted graphs.
READ FULL TEXT