Euclidean bounded-degree spanning tree ratios

ABSTRACT

Let t_K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that t₂=2 and t₅=1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103<t₃= 1.5 and 1.035<t₄= 1.25. We present the first improved upper bounds: t₃ < 1.402 and t₄ < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees.Let t_K^(d) be the analogous ratio in d-dimensional space. Khuller et al. showed that t₃^(d)<1.667 for any d. We observe that t₃^(d)<1.633.

REFERENCES

• 1: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 2: S. Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Manuscript, 2002. http://www.cs.princeton.edu/ arora/pubs/arorageo.ps.
• 3: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Tech. Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1975.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: D.-Z. Du and F. K. Hwang. A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica7121--1361992.
• 7: D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry, Elsevier Science Publishers B.V. North-Holland, Amsterdam, pages 425--461, 2000.
• 8: Sándor P. Fekete , Samir Khuller , Monika Klemmstein , Balaji Raghavachari , Neal Young, A network-flow technique for finding low-weight bounded-degree spanning trees, Journal of Algorithms, v.24 n.2, p.310-324, Aug. 1997 [doi>10.1006/jagm.1997.0862]
• 9: S. P. Fekete and H. Meijer. On minimum stars and maximum matchings. J. DCG 23:389--407, 2000.
• 10: Samir Khuller , Balaji Raghavachari , Neal Young, Low-Degree Spanning Trees of Small Weight, SIAM Journal on Computing, v.25 n.2, p.355-368, February 1996 [doi>10.1137/S0097539794264585]
• 11: J. Könemann , R. Ravi, A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.537-546, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335371]
• 12: J. N. Lillington. Some extremal properties of convex sets. J.Math. Proc. Cambridge Philosophical Society 77:515--524, 1975.
• 13: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 14: Clyde Monma , Subhash Suri, Transitions in geometric minimum spanning trees, Discrete & Computational Geometry, v.8 n.3, p.265-293, 1992 [doi>10.1007/BF02293049]
• 15: C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the traveling salesman problem. J. JAlg 5:231--246, 1984.
• 16: Balaji Raghavachari, Algorithms for finding low degree structures, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 17: R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III. Approximation algorithms for degree-constrained minimum-cost network-design problems. J.Algorithmica 31:58--78, 2001.
• 18: G. Robins and J. S. Salowe. Low-degree minimum spanning trees. J. DCG 14:151--165, 1995.
• 19: D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis. An analysis of several heuristics for the traveling salesman problem. J. SIComp 6:563--581, 1977.

INDEX TERMS

Primary 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

Additional 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

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

General Terms:
Algorithms, Theory

Keywords:
approximation, discrete geometry, minimum spanning trees