On the \(p\)-median polytope of \(Y\)-free graphs

DOI10.1016/j.disopt.2006.09.002zbMath1190.90253OpenAlexW2171417536MaRDI QIDQ951093

Mourad Baïou, Francisco Barahona

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

facility locationpolyhedral combinatorics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

On the linear relaxation of the \(p\)-median problem, On the Location and p-Median Polytopes, Variations in the flow approach to CFCLP-TC for multiobjective supply chain design, The \(p\)-median polytope of \(Y\)-free graphs: An application of the matching theory, On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convex hull of the edges of a graph and near bipartite graphs
• Computational study of large-scale \(p\)-median problems
• Polyhedral properties of the \(K\)-median problem on a tree
• The distance-domination numbers of trees
• An algorithm for finding a \(k\)-median in a directed tree
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A constant-factor approximation algorithm for the \(k\)-median problem
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• 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
• Heuristics for the fixed cost median problem
• Some facets of the simple plant location polytope
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• On the \(p\)-median polytope