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.
展开▼
机译：给定一个图 G =（ V，E ），一组端子 T⊆V 和一个度量 D 在 T 上， 0扩展问题是将 V 中的顶点分配给端子，以便在所有边上求和分配 e 端点的终端之间的距离（在D之下）中的e 最小。这个问题最早是由卡尔扎诺夫（Karzanov）研究的。 Calinescu，Karloff和Rabani基于线性规划松弛问题给出了 O （log k ）近似算法，其中 k 是数字终端。我们对此进行了改进，并给出了该问题的 O （log k / log log k ）近似算法。
展开▼
