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

Faster geometric k-point MST approximation


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
For improved accessibility of PDF content, download the file to your device.
Current View