TY - GEN

T1 - On-line Steiner trees in the Euclidean plane

AU - Alon, Noga

AU - Azar, Yossi

PY - 1992

Y1 - 1992

N2 - Suppose we are given a sequence of n points v1, . . . , vn in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. We assume that the points appear one at a time, vi arriving at step i. At the end of step i, the on-line algorithm must construct a connected graph Ti that contains the points v1, . . . , vi by connecting the new point vi to the previously constructed graph Ti-1. This can be done by joining vi (not necessarily by a straight line) to any point of Ti-1, which need not necessarily be one of the previously given points vj. The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences v1, . . . , vn as above, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points v1, . . . , vn. There are known on-line algorithms whose competitive ratio is O(log n), but there is no known nontrivial lower bound for the best possible competitive ratio. Here we prove that the upper bound is almost tight by establishing an Ω(log n/log log n) lower bound for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.

AB - Suppose we are given a sequence of n points v1, . . . , vn in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. We assume that the points appear one at a time, vi arriving at step i. At the end of step i, the on-line algorithm must construct a connected graph Ti that contains the points v1, . . . , vi by connecting the new point vi to the previously constructed graph Ti-1. This can be done by joining vi (not necessarily by a straight line) to any point of Ti-1, which need not necessarily be one of the previously given points vj. The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences v1, . . . , vn as above, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points v1, . . . , vn. There are known on-line algorithms whose competitive ratio is O(log n), but there is no known nontrivial lower bound for the best possible competitive ratio. Here we prove that the upper bound is almost tight by establishing an Ω(log n/log log n) lower bound for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.

UR - http://www.scopus.com/inward/record.url?scp=0026977996&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026977996&partnerID=8YFLogxK

U2 - 10.1145/142675.142744

DO - 10.1145/142675.142744

M3 - Conference contribution

AN - SCOPUS:0026977996

SN - 0897915178

SN - 9780897915175

T3 - Eighth Annual Symposium On Computational Geometry

SP - 337

EP - 343

BT - Eighth Annual Symposium On Computational Geometry

PB - Publ by ACM

T2 - Eighth Annual Symposium On Computational Geometry

Y2 - 10 June 1992 through 12 June 1992

ER -