A characterization of minimizable metrics in the multifacility location problem (Q1582478)

Given a metric on \(X\subset V\) (both finite) and a nonnegative weight-function \(c\) on all unordered pairs of \(V\), the minimum extension problem (a multifacility location problem) asks to find a (semi-)metric on \(V\), extending the metric on \(X\), and minimizing the sum of weighted lengths of all unordered pairs in \(V\). This is a (polynomially solvable) linear program. Such a semi-metric extension is a 0-extension if all points of \(V\) are at 0-distance from \(X\) (coincide with some point of \(X\)). Finding a minimum 0-extension is NP-hard. The metric on \(X\) is minimizable when the minimum extension problem for arbitrary supersets \(V\) and weights \(c\) yields a 0-extension. It is proven that a metric is minimizable iff it is modular (any three points admit a median) and the underlying graph (obtained by deleting from the complete graph all edges of length equal to the length of some two-edge path between them) is a frame (i.e. hereditary modular and orientable). This extends a recent Karzanov characterization of minimizable graph metrics.