Donald Bren School of Information and Computer Sciences

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+ε).