A characterization of minimizable metrics in the multifacility location problem

DOI10.1006/EUJC.1999.0378MaRDI QIDQ1582478zbMATH OpenOpenAlexFDO

Authors Hans-Jürgen Bandelt, Victor Chepoi, Alexander V. Karzanov

Publication date 30 March 2001

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/eujc.1999.0378

zbMATH Keywords

coincidencedistanceframehereditary modularmetricmultifacility location problemorientablesemi-metric

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Metric spaces, metrizability (54E35) Discrete location and assignment (90B80)

Review text

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.

Recommendations

• One more well-solved case of the multifacility location problem
• Hard cases of the multifacility location problem
• Minimum 0-extensions of graph metrics
• A multifacility location problem on median spaces
• Discrete convexity and polynomial solvability in minimum 0-extension problems

Cites work

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Hereditary modular graphs
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Minimum 0-extensions of graph metrics
• Modular Interval Spaces
• Networks with Condorcet solutions
• Six theorems about injective metric spaces
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• The Complexity of Multiterminal Cuts
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(7)

• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Hard cases of the multifacility location problem
• On tight spans for directed distances
• Metric packing for \(K_ 3 + K_ 3\)
• One more well-solved case of the multifacility location problem
• The tight span of an antipodal metric space. I: combinatorial properties
• Discrete convexity and polynomial solvability in minimum 0-extension problems

This page was built for publication: A characterization of minimizable metrics in the multifacility location problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582478)