2003 · 51 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationApproximation AlgorithmsAssignment ProblemsCombinatorial OptimizationGraph AlgorithmsInteger ProgrammingLinear ProgrammingMetric Optimization
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
9
The Complexity of Multiterminal Cuts
Elias Dahlhaus, D. S. Johnson, Christos H. Papadimitriou et al. · SIAM Journal on Computing · 1994 · 666 citations
On approximating arbitrary metrices by tree metrics
Yair Bartal · 1998 · 507 citations
The complexity of multiway cuts (extended abstract)
Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou et al. · 1992 · 221 citations · Full text