A Characterization of Minimizable Metrics in the Multifacility Location Problem

✍ Scribed by Hans-Jürgen Bandelt; Victor Chepoi; Alexander V. Karzanov

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 143 KB
• Volume: 21
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1999.0378

✦ Synopsis

In the minimum 0-extension problem (a version of the multifacility location problem), one is given a metric m on a subset X of a finite set V and a non-negative function c on the unordered pairs of elements of V . The objective is to find a semimetric m on V that minimizes the inner product c • m , provided that m coincides with m within X and each element of V is at zero distance from X . For m fixed, this problem is solvable in strongly polynomial time if m is minimizable, which means that for any superset V and function c, the minimum objective value is equal to that in the corresponding linear relaxation.

In [9], Karzanov showed that the path metric of a graph H is minimizable if and only if all isometric cycles of H have length four and the edges of H can be oriented so that non-adjacent edges in each 4-cycle have opposite orientations along the cycle (such graphs are called frames in [9]). Extending this result to general metrics m, we show that m is minimizable if and only if m is modular and its underlying graph is a frame.