Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
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.
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
D.S. Turaga, K. Ratakonda, et al.
SCC 2006
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011