Distributed near-optimal matching

DOI10.1007/BF01271265MaRDI QIDQ1375630zbMATH OpenOpenAlexFDO

Authors Xiaotie Deng

Publication date 7 January 1998

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01271265

zbMATH Keywords

randomized algorithmdistributed computingincomplete informationnear-optimal matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Recommendations

• Distributed near-optimal matching
• On the complexity of distributed stable matching with small messages
• Online bipartite matching with unknown distributions
• Fast distributed almost stable matchings
• scientific article; zbMATH DE number 176778

Cites work

• Competitive algorithms for server problems
• On the \(k\)-server conjecture

Cited in

(13)

• Distributed near-optimal matching
• Distributed Stable Matching Problems
• Improved deterministic distributed matching via rounding
• The Match-Maker: Constant-Space Distributed Majority via Random Walks
• Competitive distributed decision-making
• A lower bound for communication on the crossbar
• Distributed match-making
• Distributed stable matching with similar preference lists
• Distributed Algorithm for Better Approximation of the Maximum Matching
• scientific article; zbMATH DE number 4062556 (Why is no real title available?)
• Fast distributed almost stable matchings
• Improved Distributed Approximate Matching
• Nonlinear bipartite matching

This page was built for publication: Distributed near-optimal matching

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