Distributed near-optimal matching (Q1375630)

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.