{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T22:43:43Z","timestamp":1790289823849,"version":"4.1.0"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We study a prize-collecting version of the uncapacitated facility location problem and of the p-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the p-median and facility location problems studied in this paper.<\/jats:p>","DOI":"10.1137\/090747440","type":"journal-article","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T18:08:11Z","timestamp":1294164491000},"page":"1-20","source":"Crossref","is-referenced-by-count":1,"title":["On the\n                    <i>p<\/i>\n                    -Median Polytope and the Intersection Property: Polyhedra and Algorithms"],"prefix":"10.1137","volume":"25","author":[{"given":"Mourad","family":"Ba\u00efou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francisco","family":"Barahona","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jose","family":"Correa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,1,4]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011405"},{"key":"R2","unstructured":"M. Ba\u00efou and F. Barahona,\n                      \n                        On the Linear Relaxation\n                        p\n                        -median Problem\n                      \n                      I\n                      : Oriented Graphs\n                      , Technical report, IBM Thomas J. Watson Research Center, Yorktown Heights, NY,2007."},{"key":"R3","unstructured":"M. Ba\u00efou and F. Barahona,\n                      \n                        On the Linear Relaxation\n                        p\n                        -median Problem\n                      \n                      II\n                      : Directed Graphs\n                      , Technical report, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 2007."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/070706070"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90160-2"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.03.017"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"G. Calvillo,\n                      The concavity and intersection properties for integral polyhedra\n                      , in Combinatorics 79, Part I, Ann. Discrete Math. 8, North-Holland, Amsterdam, 1980, pp. 221\u2013228.","DOI":"10.1016\/S0167-5060(08)70877-X"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00328-6"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592196"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.579"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.590"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703405754"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"G. Cornuejols, M. L. Fisher, and G. L. Nemhauser,\n                      Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms\n                      , Manag. Sci., 23 (1976\/77), pp. 789\u2013810.","DOI":"10.1287\/mnsc.23.8.789"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01583779"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00062-1"},{"key":"R16","unstructured":"C. De Simone and C. Mannino,\n                      Easy Instances of the Plant Location Problem\n                      , Technical report R. 427, Institute for Systems Analysis and Computer Science, Consiglio, Nationale delle Ricerche, Rome, Italy, 1996."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. Guignard,\n                      Fractional vertices, cuts and facets of the simple plant location problem\n                      , in Combinatorial optimization, Math. Program. Stud. 12, Springer, New York, 1980, pp. 150\u2013162.","DOI":"10.1007\/BFb0120893"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580723"},{"key":"R20","unstructured":"P. B. Mirchandani and R. L. Francis, eds.\n                      Discrete location theory\n                      , Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1990."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580121"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"R23","unstructured":"W. Pulleyblank,\n                      Faces of Matching Polyhedra\n                      , Ph. D. thesis, University of Waterloo, Waterloo, Ontario, 1973."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"W. Pulleyblank and J. Edmonds,\n                      Facets of 1-matching polyhedra\n                      , in Hypergraph Seminar, Lecture Notes in Math. 411, Springer, Berlin, 1974, pp. 214\u2013242.","DOI":"10.1007\/BFb0066196"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. Aardal,\n                      Approximation algorithms for facility location problems (extended abstract)\n                      , in Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"M. Sviridenko,\n                      An improved approximation algorithm for the metric uncapacitated facility location problem\n                      , in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 2337, Springer, Berlin, 2002, pp. 240\u2013257.","DOI":"10.1007\/3-540-47867-1_18"},{"key":"R27","unstructured":"J. Vygen,\n                      Approximation Algorithms for Facility Location Problems\n                      , Technical report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, Bonn, Germany, 2005."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090747440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:35:37Z","timestamp":1787319337000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090747440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090747440"],"URL":"https:\/\/doi.org\/10.1137\/090747440","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}