Prefer a chat interface with context about you and your work?
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.