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

distributed computingincomplete informationnear-optimal matchingrandomized algorithm

Mathematics Subject Classification ID

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

Review text

A novel bipartite matching problem, motivated by recent interests in computational problems under incomplete information is discussed. The competitive analysis, comparing a solution obtained under partial information with the optimal solution under complete information for the same set of input data is applied. For the distributed matching problem it is assumed that none of the boys (left nodes of a bipartite graph) communicate with others. This matching problem is typical of distributed computing under incomplete information: Each boy only knows his own preference but none of the others. He may coordinate his strategy with those of the other boys but only as a function of his own information. Because of this restriction, any deterministic algorithm involving one round of proposals may end up with a matching which is contact in size - and arbitrarily smaller than the optimum matching size \(M\). However, it is shown that a simple randomized algorithm matches at least \(\Omega (\sqrt M)\) pairs.

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