1995/04/01 by Michel X. Goemans, David P. Williamson · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Travelling salesman problem #Steiner tree problem #Approximation algorithm #Mathematics #Combinatorics #Triangle inequality #Shortest path problem #Matching (statistics) #Time complexity #Connection (principal bundle) #Binary logarithm #Covering problems #Discrete mathematics #Mathematical optimization #Graph #Computer science
paper · doi:10.1137/s0097539793242618
openalex publication_date 1995/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 fit 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(n2 log n) time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of O(n2 log n) time compares favorably with the best strongly polynomial exact algorithms running in O(n3) 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–4201.