Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
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.
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Jianke Yang, Robin Walters, et al.
ICML 2023