Weighted Matchings via Unweighted Augmentations

DOI10.1145/3293611.3331603MaRDI QIDQ5145261zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

parallel algorithmsweighted matchingsemi-streamingMpc

Mathematics Subject Classification ID

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

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

Cited in

(4)

• Weighted restricted 2-matching
• Maliciously secure massively parallel computation for all-but-one corruptions
• 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)