Simple Polynomial-Time Approximation Schemes for Geometric Network Optimization Problems

by Joe Mitchell (State University of New York Stony Brook, NY 11794-3600)

Abstract. We present simple polynomial-time approximation schemes for geometric instances of the k-MST problem, the traveling salesman problem (TSP), and other network optimization problems.

Our method is based on the concept of an ``m-guillotine subdivision''. Roughly speaking, an ``m-guillotine subdivision'' is a polygonal subdivision with the property that there exists a line (``cut''), whose intersection with the subdivision edges consists of a small number (O(m)) of connected components, and the subdivisions on either side of the line are also m-guillotine. The upper bound on the number of connected components allows one to apply dynamic programming to optimize over m-guillotine subdivisions, as there is a succinct specification of how the subdivision interacts with the cuts that make up the boundary of a rectangle that specifies a subproblem of the dynamic program.

Key to our method is a theorem, with a simple proof, showing that any polygonal subdivision can be converted into an m-guillotine subdivision by adding a set of edges whose total length is small: at most that of the original subdivision, times . This allows us to apply dynamic programming to optimize over the class of m-guillotine subdivisions having some prescribed properties, since the relevant subproblems are specified by only a constant (O(m)) number of parameters. This yields a -approximation algorithm for various network optimization problems (k-MST, TSP, etc.), which has running time

We present also a recent modification to our main theorem, which allows the running time to be improved substantially: we obtain a deterministic -time algorithm. Further, we discuss other generalizations of our techniques to variants of the Euclidean TSP.

(paper available at http://ams.sunysb.edu/ jsbm/jsbm.html)