Distributed near-optimal matching (Q1375630)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distributed near-optimal matching |
scientific article |
Statements
Distributed near-optimal matching (English)
0 references
7 January 1998
0 references
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.
0 references
near-optimal matching
0 references
distributed computing
0 references
incomplete information
0 references
randomized algorithm
0 references