A GENERAL APPROXIMATION TECHNIQUE FOR CONSTRAINED FOREST PROBLEMS

We present a general approximation technique for a large class of grap h problems. Our technique mostly applies to problems of covering, at m inimum cost, the vertices of a graph with trees, cycles, or paths sati sfying certain requirements. In particular, many basic combinatorial o ptimization problems lit in this framework, including the shortest pat h, minimum-cost spanning tree, minimum-weight perfect matching, travel ing salesman, and Steiner tree problems. Our technique produces approx imation algorithms that run in O (n(2) log n) time and come within a f actor of 2 of optimal for most of these problems. For instance, we obt ain a a-approximation algorithm for the minimum-weight perfect matchin g problem under the triangle inequality. Our running time of O (n(2) l og 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 deri ve the first approximation algorithms for many NP-complete problems, i ncluding the nonfixed point-to-point connection problem, the exact pat h 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 previo usly best-known performance guarantees of 2.5 and 3, respectively [Mat h. Programming, 59 (1993), pp. 413-420].