Polyhedral properties of the K-median problem on a tree

DOI10.1007/S10107-006-0002-7zbMATH Open1130.90058OpenAlexW2086058434MaRDI QIDQ879965FDOQ879965

Rakesh V. Vohra, Sven De Vries, Marc E. Posner

Publication date: 10 May 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0002-7

zbMATH Keywords

polyhedral combinatoricsfacetsvalid inequalities\(K\)-median problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

• Title not available (Why is that?)
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Local search heuristic for k-median and facility location problems
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• Packing and covering a tree by subtrees
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• Some facets of the simple plant location polytope
• On the \(p\)-median polytope

Cited In (8)

• Some polynomially solvable cases of the inverse ordered 1-median problem on trees
• A large class of facets for the \(K\)-median polytope
• On the linear relaxation of the \(p\)-median problem
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• On the \(p\)-median polytope of \(Y\)-free graphs
• Depth functions and mutidimensional medians on minimal spanning trees
• Title not available (Why is that?)
• A polynomial method for the pos/neg weighted 3-median problem on a tree

Recommendations

• Title not available (Why is that?) 👍 👎
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs 👍 👎
• Some polynomially solvable cases of the inverse ordered 1-median problem on trees 👍 👎
• The nestedness property of the convex ordered median location problem on a tree 👍 👎
• Some properties of a polyhedron for the \(p\)-median problem 👍 👎
• On the Steiner median of a tree 👍 👎
• A polynomial algorithm for the two-connections variant of the tree \(p\)-median problem 👍 👎
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem 👍 👎
• On Parametric Medians of Trees 👍 👎
• Median and hybrid median \(K\)-dimensional trees 👍 👎

This page was built for publication: Polyhedral properties of the \(K\)-median problem on a tree

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