An improved approximation algorithm for the 0-extension problem

ABSTRACT

Given a graph G = (V, E), a set of terminals T ⊆ V, and a metric D on T, the 0-extension problem is to assign vertices in V to terminals, so that the sum, over all edges e, of the distance (under D) between the terminals to which the end points of e are assigned, is minimized. This problem was first studied by Karzanov. Calinescu, Karloff and Rabani gave an O(logk) approximation algorithm based on a linear programming relaxation for the problem, where k is the number of terminals. We improve on this bound, and give an O(log k/log log k) approximation algorithm for the problem.

REFERENCES

• 1: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 2: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 3: Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
• 4: Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for multiway cut, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.48-52, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276711]
• 5: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 6: William H. Cunningham , Lawrence Tang, Optimal 3-Terminal Cuts and Linear Programming, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.114-125, June 09-11, 1999
• 7: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The complexity of multiway cuts (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.241-251, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129736]
• 8: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 9: Anupam Gupta , Éva Tardos, A constant factor approximation algorithm for a class of classification problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.652-658, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335397]
• 10: Alexander V. Karzanov, Minimum 0-extensions of graph metrics, European Journal of Combinatorics, v.19 n.1, p.71-101, Jan., 1998 [doi>10.1006/eujc.1997.0154 ]
• 11: David R. Karger , Philip Klein , Cliff Stein , Mikkel Thorup , Neal E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.668-678, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301430]
• 12: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 13: {Mat} J. Matoušek. Open Problems on embeddings of finite metric spaces. Workshop on discrete metric spaces and their algorithmic applications, 2002. Available at http://kam.mff.cuni.cz/~matousek/haifaop.ps.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory