Distributed near-optimal matching (Q1375630): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Xiaotie Deng / rank | |||
Property / author | |||
Property / author: Xiaotie Deng / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the <i>k</i>-server conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Competitive algorithms for server problems / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01271265 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2024165970 / rank | |||
Normal rank |
Latest revision as of 09:48, 30 July 2024
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