On-line Steiner trees in the Euclidean plane

ABSTRACT

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-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 &OHgr;(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.

REFERENCES

• BM: B. Bollob&s and A. Meir, A traveling salesman problem in the k-dimensional unit cube, Operations Research Letters, to appear.
• BS: J.L. Bentley and J.B. Saxe, An analysis of two heuristics for the Euclidean Traveling salesman, 18th Annual Allcrton Conference on Communication, Control and Computing, Monticello, 1980, pp. 41-49.
• CV: B. Chandra and S. Vishwanathan, Constructing reliable communication networks of small weight on-line, 1991, Manuscript.
• IW: M. Imase and B.M. Waxman, Dynamic Steiner tree problem, SIAM J. Disc Math. d, (199t), pp. 369-384.
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Me: A. Meir, A geometric problem involving the nearest neighbor algorithm, Operations Research Letters 6 (1987), pp. 289-291.
• Ne: D.J. Newman, A problem seminar, Springer, Berlin 1982, 9, Problem 57.
• RSL: D.J. Rosenkrantz, R.E. Strearns and P.M. Lewis II, An analysis of several heuristics for the traveling salesman problem, SlAM J. Computing 6, (1977), pp. 563~581.
• ST: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• Wi: P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]
• Ya: A.C.C. Y~o, Probabilistic computation: towards a unified measure of complexity, Proc. 18th Annual IEEE FOCS, Providence, RI (1977), pp. 222-227.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory