On the linear relaxation of the p-median problem

DOI10.1016/J.DISOPT.2010.12.002zbMATH Open1242.90272OpenAlexW1971059215MaRDI QIDQ429694FDOQ429694

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)