Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space

DOI10.1016/0020-0190(94)00116-2zbMath0941.68591OpenAlexW1968225281MaRDI QIDQ1336762

Yunn Yen Chen, Ying The Tsai, Chuan Yi Tang

Publication date: 26 February 1996

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00116-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

The online transportation problem

Cites Work

• Unnamed Item
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• A competitive 2-server algorithm
• An average case analysis of a greedy algorithm for the on-line Steiner tree problem
• An upper bound for the average length of the euclidean minimum spanning tree
• Online Weighted Matching

This page was built for publication: Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space