The metric relaxation for <i>0</i> -extension admits an <i> Ω(log <sup>2/3</sup> k) </i> gap
The metric relaxation for <i>0</i> -extension admits an <i> Ω(log <sup>2/3</sup> k) </i> gap
We consider the 0-Extension problem, where we are given an undirected graph G=(V,E) equipped with non-negative edge weights w:E→ ℝ+, a collection T={ t1,…,tk}⊆ V of k special vertices called terminals, and a semi-metric D over T. The goal is to assign every non-terminal vertex to a terminal while minimizing …