An improved approximation algorithm for the 0-extension problem
Jittat Fakcharoenphol, Chris Harrelson, Satish B. Rao, Kunal Talwar · 2003
Abstract Given a graph G = (V, E), a set of terminals T ` V, anda metric D on T, the 0-extension problem is to assignvertices in V to terminals, so that the sum, over all edges e, of the distance (under D) between the terminals towhich the end points of e are assigned, is minimized.This problem was first studied by Karzanov. Calinescu, Karloff and Rabani gave an O(log k) approximationalgorithm based on a linear programming relaxation for the problem, where k is the number of terminals. Weimprove on this bound, and give an O(log k / log log k)approximation algorithm for the problem. 1 Introduction In the 0-extension problem, we are given an undirectedgraph G = (V, E) with costs c(u, v) on edges, a setof terminals