On the Linear Relaxation of the p-Median Problem

We study a well-known linear programming relaxation of the p-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 p-median problem is polynomial in that class of graphs. We also give an algorithm to recognize these graphs.

By: Mourad Baïou; Francisco Barahona

Published in: Discrete Optimization, volume 8, (no 2), pages 344-75 in 2011

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .