On the linear relaxation of the p-median problem

DOI10.1016/J.DISOPT.2010.12.002MaRDI QIDQ429694zbMATH OpenOpenAlexFDO

Authors Mourad Baïou, Francisco Barahona

Publication date 20 June 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2010.12.002

zbMATH Keywords

\(p\)-median problemodd cycleuncapacitated facility location problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Recommendations

• On the \(p\)-median polytope and the odd directed cycle inequalities: oriented graphs
• On the location and \(p\)-median polytopes
• On the \(p\)-median polytope and the directed odd cycle inequalities
• On the \(p\)-median polytope of \(Y\)-free graphs
• On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem
• A family of facets for the uncapacitated \(p\)-median polytope
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An algorithm for finding a \(k\)-median in a directed tree
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Fractional vertices, cuts and facets of the simple plant location problem
• Integer Programming: Methods, Uses, Computations
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• On the \(p\)-median polytope
• On the \(p\)-median polytope of \(Y\)-free graphs
• On the facets of the simple plant location packing polytope
• On the integrality of some facility location polytopes
• Polyhedral properties of the \(K\)-median problem on a tree
• Solution methods for thep-median problem: An annotated bibliography
• Solving the plant location problem on a line by linear programming
• Some facets of the simple plant location polytope
• The \(p\)-median polytope of \(Y\)-free graphs: An application of the matching theory

Cited in

(10)

• scientific article; zbMATH DE number 1416475 (Why is no real title available?)
• On the \(p\)-median polytope and the intersection property: polyhedra and algorithms
• A large class of facets for the \(K\)-median polytope
• On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs
• On the \(p\)-median polytope and the odd directed cycle inequalities: oriented graphs
• On the Vector Assignment p-Median Problem
• Discretization and resolution of the \((r| X_ p)\)-medianoid problem involving quality criteria.
• On a connection between facility location and perfect graphs
• An efficient Benders decomposition for the \(p\)-median problem
• On the location and \(p\)-median polytopes

This page was built for publication: On the linear relaxation of the \(p\)-median problem

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