Weighted Matchings via Unweighted Augmentations

DOI10.1145/3293611.3331603OpenAlexW2963298291MaRDI QIDQ5145261FDOQ5145261

Authors: Buddhima Gamlath, Sagar Kale, Slobodan Mitrović, Ola Svensson 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.02760

Recommendations

• Improved streaming algorithms for weighted matching, via unweighted matching
• Weighted matching in the semi-streaming model
• Weighted matching in the semi-streaming model
• A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
• A \((2+\epsilon)\)-approximation for maximum weight matching in the semi-streaming model

zbMATH Keywords

parallel algorithmsweighted matchingsemi-streamingMpc

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (4)

• Maliciously secure massively parallel computation for all-but-one corruptions
• Weighted restricted 2-matching
• Improved bounds for matching in random-order streams
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings

This page was built for publication: Weighted Matchings via Unweighted Augmentations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145261)