A characterization of minimizable metrics in the multifacility location problem
type: Item
instance of: scholarly article
title: A characterization of minimizable metrics in the multifacility location problem
zbMATH Open document ID: 0958.05045
author: Hans-Jürgen Bandelt
author: Victor Chepoi
author: Alexander V. Karzanov
published in: European Journal of Combinatorics
publication date: 2001-03-30T00:00:00Z
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.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 54E35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 1513382
zbMATH Keywords: multifacility location problem
zbMATH Keywords: distance
zbMATH Keywords: coincidence
zbMATH Keywords: metric
zbMATH Keywords: hereditary modular
zbMATH Keywords: orientable
zbMATH Keywords: frame
zbMATH Keywords: semi-metric
MaRDI profile type: Publication
full work available at URL: eujc.1999.0378
OpenAlex ID: W2064393153
cites work: Networks with Condorcet solutions
cites work: Hereditary modular graphs
cites work: Modular Interval Spaces
cites work: The Complexity of Multiterminal Cuts
cites work: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
cites work: Q5514188
cites work: Six theorems about injective metric spaces
cites work: Minimum 0-extensions of graph metrics
cites work: State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
DOI: 10.1006/EUJC.1999.0378
description: scientific article; zbMATH DE number 1513382