Logo image
Back
Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space
Journal article   Peer reviewed

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

Ying The Tsai, Chuan Yi Tang and Yunn Yen Chen
Information Processing Letters, Vol.51(6), pp.275-282
09/1994
DOI: https://doi.org/10.1016/0020-0190(94)00116-2

Abstract

Analysis of algorithms Average case analysis On-line algorithms The on-line minimum matching problem Theoretical Computer Science Signal Processing Information Systems Computer Science Applications
In this paper, we consider the average performance analysis of a simple greedy algorithm for solving the on-line minimum matching problem on Euclidean space. The algorithm has been shown to be (2 n - 1)-competitive, where 2n is the total number of points in the plane. However, we show that the average matching cost incurred by the algorithm is bounded by 2.3 n times the average cost of the optimal minimum matching when the number of points is large (100 points is sufficiently large in our experiment). © 1994.

Metrics

1 Record Views

Details

Logo image