An improved approximation algorithm for the 0-extension problem

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal TalwarSODA 2003 · OpenReview

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.
BibTeX
@inproceedings{fakcharoenphol2003improved,
  author = {Jittat Fakcharoenphol and Chris Harrelson and Satish Rao and Kunal Talwar},
  title = {{An improved approximation algorithm for the 0-extension problem}},
  booktitle = {SODA},
  year = {2003},
  url = {https://openreview.net/forum?id=imp5TmpgGA},
}

Loading related content...

Figure