AVERAGE COMPETITIVE RATIOS OF ONLINE SPANNING-TREES

Authors
BAO F MEI AH IGARASHI Y
Citation
F. Bao et al., AVERAGE COMPETITIVE RATIOS OF ONLINE SPANNING-TREES, Information processing letters, 62(4), 1997, pp. 213-216
Citations number
4
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
62
Issue
4
Year of publication
1997
Pages
213 - 216
Database
ISI
SICI code
0020-0190(1997)62:4<213:ACROOS>2.0.ZU;2-P
Abstract
We study the average competitive ratio of on-line spanning trees with the same distribution of points in the Euclidean plane. We show a dist ribution of n points such that the average competitive ratio of on-lin e spanning trees by any on-line algorithm cannot be less than 1/4 ln n - 1/2. (C) 1997 Elsevier Science B.V.