Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141512 | Discrete Optimization | 2011 | 32 Pages |
Abstract
We study a well-known linear programming relaxation of the pp-median problem. We give a characterization of the directed graphs for which this system of inequalities defines an integral polytope. As a consequence, we obtain that the pp-median problem is polynomial in that class of graphs. We also give an algorithm to recognize these graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Mourad Baïou, Francisco Barahona,