On the p-media polytope of special class of graphs

Mourad Baïou () and Fancisco Barahona
Additional contact information
Mourad Baïou: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique
Fancisco Barahona: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique

Working Papers from HAL

Abstract: In this paper we consider a well known class of valid inequalities for the p-median and the uncapacitated facility location polytopes, the odd cycle inequalities. It is known that their separation problem is polynomially solvable. We give a new polynomial separation algorithm based on a reduction from the original graph. Then, we define a nontrivial class of graphs, where the odd cycle inequalities together with the linear relaxations of both the p-median and uncapacitated facility location problems, suffice to describe the associated polytope. To do this, we first give a complete description of the fractional extreme points of the linear relaxation for the p-median polytope in that class of graphs.

Date: 2005
Note: View the original document on HAL open archive server: https://hal.science/hal-00242976
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://hal.science/hal-00242976/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-00242976

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().