Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
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. © 2011 Elsevier B.V. All rights reserved.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence