A GENERAL APPROXIMATION TECHNIQUE FOR CONSTRAINED FOREST PROBLEMS

We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles, or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems lit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman, and Steiner tree problems. Our technique produces approximation algorithms that run in O (n(2) log n) time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a a-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of O (n(2) log n) time compares favorably with the best strongly polynomial exact algorithms running in O (n(3)) time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the nonfixed point-to-point connection problem, the exact path partitioning problem, and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 413-420].