Similar Elements and Metric Labeling on Complete Graphs

We consider a problem that involves finding similar elements in a collection of sets. Let X be a (possibly infinite) set and d be a metric on X. Let $* argininx C(LB) be an optimal solution for the similar elements problem. In particular we define n different "star--graph" objective For each 1 S 7" S n define the objective CT(:E) to account only for the terms in C((L') involving 33,1, Let 3:" argminx Cr (:13) be an optimal solution for the optimization problem defined by Cr (x). We can compute x7" efficiently using a simple form of dynamic programming, by first computing (E; Each of the n "star--graph" Objective functions leads to a possible solution. Let G (V, E) be an undirected simple graph on n nodes V {1, . . . Let 33* argininm C(CL') This optimization problem can be solved in polynomial time using For each 7" E V define a different objective function, CT (:13), corresponding to a metric labeling Let SET 2 argininm CT (x).