Polyhedral properties of the \(K\)-median problem on a tree
type: Item
instance of: scholarly article
title: Polyhedral properties of the \(K\)-median problem on a tree
zbMATH Open document ID: 1130.90058
author: Marc E. Posner
author: Rakesh V. Vohra
author: Sven De Vries
published in: Mathematical Programming. Series A. Series B
publication date: 2007-05-10T00:00:00Z
review text: This paper investigates the polyhedral structure of the \(K\)-median problem on trees. Despite the problem being solvable in polynomial time, no exact LP formulation is known. The authors give an IP formulation and show that for every tree with at least 4 vertices there is a dataset such that the polytope \(Q_K\) of the LP relaxation of this formulation is not integral for all \(K \geq 2\). They investigate the structure of \(Q_K\) and show that \(x^{\text{LP}}=z^*\) if \(T\) is a path or a 1-star and that these are the only trees with this property. Furthermore, for general graphs, \(Q_K\) is shown to be integral if and only if \(K\in \{1,n-1, n\}\). The authors also show that \(z^*/z^{LP} < 2-2/(K+1)\) and that this bound is asymptotically tight. Next, they give a new proof that an alternative formulation for \(K=2\) is integral. This is followed by the identification of a class of constraints that they demonstrate to result in integer polytopes for all \(K\) if \(T\) is a 1-star. Finally, a class of facets for general graphs and \(K\geq 2\) is established. This class is then used to prove integrality of a new description of the problem for 2-stars.
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 52B05
zbMATH DE Number: 5151336
zbMATH Keywords: \(K\)-median problem
zbMATH Keywords: polyhedral combinatorics
zbMATH Keywords: facets
zbMATH Keywords: valid inequalities
MaRDI profile type: Publication
full work available at URL: s10107-006-0002-7
OpenAlex ID: W2086058434
cites work: Local search heuristic for k-median and facility location problems
cites work: On the \(p\)-median polytope
cites work: Packing and covering a tree by subtrees
cites work: On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
cites work: Some facets of the simple plant location polytope
cites work: Q3971521
cites work: An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
cites work: An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
DOI: 10.1007/S10107-006-0002-7
Recommended article: Q4779149
Recommended article: An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
Recommended article: Median and hybrid median \(K\)-dimensional trees
Recommended article: On the Steiner median of a tree
Recommended article: The nestedness property of the convex ordered median location problem on a tree
Recommended article: Some properties of a polyhedron for the \(p\)-median problem
Recommended article: Some polynomially solvable cases of the inverse ordered 1-median problem on trees
Recommended article: A polynomial algorithm for the two-connections variant of the tree \(p\)-median problem
Recommended article: Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
Recommended article: On Parametric Medians of Trees
description: scientific article; zbMATH DE number 5151336