Skip to main content
eScholarship
Open Access Publications from the University of California

Faster geometric k-point MST approximation

  • Author(s): Eppstein, David
  • et al.
Abstract

We give fast new approximation algorithms for the problem of choosing k planar points out of n to minimize the length of their minimum spanning tree (equivalently, of their traveling salesman tour or Steiner tree). For any x =/< k, we can find an approximation achieving approximation ratio O(log k/log x) in time O(n log n + 2^x kn log k). In particular, we get an approximation with ratio O(log k / log log n) in time O(kn^(1+ε).

Main Content
Current View