Randomized algorithms for the on-line minimum matching problem on euclidean space

DOI10.1080/00207169508804431zbMath0847.68051OpenAlexW2019170215MaRDI QIDQ4876378

Ying Teh Tsai, Yunn Yen Chen, Chuan Yi Tang

Publication date: 7 October 1996

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169508804431

zbMATH Keywords

competitive analysisminimum matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• The average-case analysis of some on-line algorithms for bin packing
• A competitive 2-server algorithm
• Average-case analysis of the modified harmonic algorithm
• An upper bound for the average length of the euclidean minimum spanning tree
• A stochastic model of bin-packing
• Online Weighted Matching

This page was built for publication: Randomized algorithms for the on-line minimum matching problem on euclidean space