Euclidean bounded-degree spanning tree ratios

Research output: Contribution to conferencePaper

Abstract

Let τ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 τ2 = 2 and τ5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < τ3 ≤ 1.5 and 1.035 < τ4 ≤ 1.25. We present the first improved upper bounds: τ3 < 1.402 and τ4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let τk(d) be the analogous ratio in d-dimensional space. Khuller et al. showed that τ3(d) < 1.667 for any d. We observe that τ3(d) < 1.633.

Original languageEnglish (US)
Pages11-19
Number of pages9
DOIs
StatePublished - Jan 1 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003

Other

OtherNineteenth Annual Symposium on Computational Geometry
CountryUnited States
Citysan Diego, CA
Period6/8/036/10/03

Keywords

  • Approximation
  • Discrete geometry
  • Minimum spanning trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Euclidean bounded-degree spanning tree ratios'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M. (2003). Euclidean bounded-degree spanning tree ratios. 11-19. Paper presented at Nineteenth Annual Symposium on Computational Geometry, san Diego, CA, United States. https://doi.org/10.1145/777793.777795