An improved approximation algorithm for the 0-extension problem
Lists
Only you see this
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...