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

Mpcparallel algorithmssemi-streamingweighted matching

Mathematics Subject Classification ID

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

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

(18)

• Weighted restricted 2-matching
• Maliciously secure massively parallel computation for all-but-one corruptions
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Improved bounds for matching in random-order streams
• Constructing large matchings via query access to a maximal matching oracle
• Robust algorithms under adversarial injections
• Improved bounds for matching in random-order streams
• A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
• Weighted matching in the random-order streaming and robust communication models
• Maximum weight b-matchings in random-order streams
• Exponentially faster massively parallel maximal matching
• Beating two-thirds for random-order streaming matching
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• Semi-streaming algorithms for weighted k-disjoint matchings
• Improved approximation algorithms for (1,2)-TSP and Max-TSP using path covers in the semi-streaming model
• Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries
• Weighted matching in a poly-streaming model
• Almost optimal superconstant-pass streaming lower bounds for reachability

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)