F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
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 non-trivial 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 this class of graphs. © 2007 Elsevier Ltd. All rights reserved.
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences