{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089180,"version":"3.41.0"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,5,31]],"date-time":"2015-05-31T00:00:00Z","timestamp":1433030400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10107-015-0916-z","type":"journal-article","created":{"date-parts":[[2015,5,30]],"date-time":"2015-05-30T06:22:13Z","timestamp":1432966933000},"page":"99-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Integrality gaps for strengthened linear relaxations of capacitated facility location"],"prefix":"10.1007","volume":"158","author":[{"given":"Stavros G.","family":"Kolliopoulos","sequence":"first","affiliation":[]},{"given":"Yannis","family":"Moysoglou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,31]]},"reference":[{"key":"916_CR1","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1287\/moor.20.3.562","volume":"20","author":"K Aardal","year":"1995","unstructured":"Aardal, K., Pochet, Y., Wolsey, L.A.: Capacitated facility location: valid inequalities and facets. Math. Oper. Res. 20, 562\u2013582 (1995)","journal-title":"Math. Oper. Res."},{"key":"916_CR2","first-page":"253","volume":"21","author":"K Aardal","year":"1996","unstructured":"Aardal, K., Pochet, Y., Wolsey, L.A.: Erratum: capacitated facility location: valid inequalities and facets. Math. Oper. Res. 21, 253\u2013256 (1996)","journal-title":"Math. Oper. Res."},{"key":"916_CR3","unstructured":"Abrams, Zo\u00eb, M., Adam, M., Kamesh, P., Serge: The integrality gap of capacitated facility location. Technical Report CMU-CS-02-199, Carnegie Mellon University (2002)"},{"issue":"1\u20132","key":"916_CR4","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s10107-012-0565-4","volume":"141","author":"A Aggarwal","year":"2013","unstructured":"Aggarwal, A., Louis, A., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program. 141(1\u20132), 527\u2013547 (2013)","journal-title":"Math. Program."},{"key":"916_CR5","doi-asserted-by":"crossref","unstructured":"An, H.-C., Bhaskara, A., Svensson, O.: Centrality of trees for capacitated k-center. CoRR, arXiv:1304.2983 , (2013)","DOI":"10.1007\/978-3-319-07557-0_5"},{"key":"916_CR6","doi-asserted-by":"crossref","unstructured":"An, H.-C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS \u201914, pp. 256\u2013265. IEEE Computer Society, Philadelphia, PA, USA (2014)","DOI":"10.1109\/FOCS.2014.35"},{"key":"916_CR7","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L.: Proving integrality gaps without knowing the linear program. In: Proceedings of the 43rd Symposium on Foundations of ComputerScience, FOCS \u201902, pp. 313\u2013322. IEEE Computer Society, Washington, DC, USA (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"issue":"1","key":"916_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"S Arora","year":"2006","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory Comput. 2(1), 19\u201351 (2006)","journal-title":"Theory Comput."},{"issue":"3","key":"916_CR9","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G.: A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math. Program. 58(3), 295\u2013324 (1993)","journal-title":"Math. Program."},{"key":"916_CR10","doi-asserted-by":"crossref","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: Epstein L., Ferragina P. (eds.), Algorithms ESA 2012, Volume 7501 of Lecture Notes in Computer Science, pp. 133\u2013144. Springer, Berlin, Heidelberg (2012)","DOI":"10.1007\/978-3-642-33090-2_13"},{"key":"916_CR11","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th annual ACM Symposium on Theory of computing, STOC \u201906, pp. 31\u201340. ACM, New York, NY, USA (2006)","DOI":"10.1145\/1132516.1132522"},{"issue":"3","key":"916_CR12","doi-asserted-by":"crossref","first-page":"20:1","DOI":"10.1145\/2229163.2229164","volume":"8","author":"M Bateni","year":"2012","unstructured":"Bateni, M., Hajiaghayi, M.: Assignment problem in content distribution networks: unsplittable hard-capacitated facility location. ACM Trans. Algorithms 8(3), 20:1\u201320:19 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"916_CR13","doi-asserted-by":"crossref","unstructured":"Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. In: Proceedings of 13th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 288\u2013302. (2008)","DOI":"10.1007\/978-3-540-68891-4_20"},{"key":"916_CR14","unstructured":"Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, pp. 106\u2013115. San Francisco, CA, USA (2000)"},{"key":"916_CR15","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201913, 26\u201329 October, 2013, pp. 350\u2013359. Berkeley, CA, USA (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"916_CR16","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201999, pp. 378\u2013388, (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"916_CR17","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the 41st annual ACM Symposium on Theory of Computing, STOC \u201909, pp. 283\u2013292. ACM, New York, NY, USA (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"916_CR18","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: Proceedings of the 10th annual ACM-SIAM symposium on Discrete algorithms, SODA \u201999, pp. 875\u2013876. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"issue":"2","key":"916_CR19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"FA Chudak","year":"2005","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207\u2013222 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"916_CR20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10479-012-1269-0","volume":"204","author":"M Conforti","year":"2013","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. Ann. Oper. Res. 204(1), 97\u2013143 (2013)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"916_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-006-0086-0","volume":"112","author":"G Cornu\u00e9jols","year":"2008","unstructured":"Cornu\u00e9jols, G.: Valid inequalities for mixed integer linear programs. Math. Program. 112(1), 3\u201344 (2008)","journal-title":"Math. Program."},{"key":"916_CR22","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for $$k$$ k -centers with non-uniform hard capacities. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201912, October 20\u201323, 2012, pp. 273\u2013282. New Brunswick, NJ, USA (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"916_CR23","unstructured":"Fernandez de la Vega, W., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 53\u201361. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2007)"},{"key":"916_CR24","unstructured":"Georgiou, K., Magen, A.: Limitations of the Sherali\u2013Adams lift and project system: compromising local and global arguments. Technical Report CSRG-587, University of Toronto (2008)"},{"issue":"4","key":"916_CR25","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4), 796\u2013815 (2001)","journal-title":"Math. Oper. Res."},{"key":"916_CR26","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"916_CR27","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22, 148\u2013162 (1982)","journal-title":"Math. Program."},{"issue":"6","key":"916_CR28","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"916_CR29","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"916_CR30","unstructured":"Kolliopoulos, S.G., Moysoglou, Y.: Extended formulation lower bounds via hypergraph coloring? To appear in Proceedings of 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, Munich, Germany (2015)"},{"key":"916_CR31","unstructured":"Kolliopoulos, S.G., Moysoglou, Y.: Exponential lower bounds on the size of approximate formulations in the natural encoding for capacitated facility location. CoRR, arXiv:1312.1819 , (2013)"},{"key":"916_CR32","unstructured":"Kolliopoulos, S.G., Moysoglou, Y.: Integrality gaps for strengthened LP relaxations of capacitated and lower-bounded facility location. CoRR, arXiv:1305.5998 , (2013)"},{"key":"916_CR33","unstructured":"Kolliopoulos, S.G., Moysoglou, Y.: Sherali\u2013Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location CoRR, arXiv:1312.0722 , (2013)"},{"key":"916_CR34","unstructured":"Kolliopoulos, S.G., Moysoglou, Y.: Sherali\u2013Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014, pp. 297\u2013312. Barcelona, Spain (2014)"},{"key":"916_CR35","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201998, pp. 1\u201310. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1998)"},{"key":"916_CR36","doi-asserted-by":"crossref","unstructured":"Lasserre Jean B.: An explicit exact SDP relaxation for nonlinear 0\u20131 programs. In: Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 293\u2013303, London, UK (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"3","key":"916_CR37","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali\u2013Adams, Lov\u00e1sz\u2013Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"1\u20133","key":"916_CR38","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF01587093","volume":"44","author":"JMY Leung","year":"1989","unstructured":"Leung, J.M.Y., Magnanti, T.L.: Valid inequalities and facets of the capacitated plant location problem. Math. Program. 44(1\u20133), 271\u2013291 (1989)","journal-title":"Math. Program."},{"key":"916_CR39","unstructured":"Levi, R., Shmoys, D.B., Swamy, C.: LP-based approximation algorithms for capacitated facility location. Math Program, 131(1\u20132):365\u2013379, 2012. Preliminary version in Proc. IPCO (2004)"},{"key":"916_CR40","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45\u201358 (2013)","journal-title":"Inf. Comput."},{"key":"916_CR41","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. In: Dan, B., Tim, R., Joan, F. (eds.) Proceedings of 45th ACM Symposium on Theory of Computing, STOC \u201913, pp. 901\u2013910. ACM (2013)","DOI":"10.1145\/2488608.2488723"},{"key":"916_CR42","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"916_CR43","doi-asserted-by":"crossref","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Battista, G., Zwick, U. (eds.) Algorithms\u2014ESA 2003, Volume 2832 of Lecture Notes in Computer Science, pp. 409\u2013421. Springer, Berlin, Heidelberg (2003)","DOI":"10.1007\/978-3-540-39658-1_38"},{"issue":"2","key":"916_CR44","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"916_CR45","doi-asserted-by":"crossref","unstructured":"Martin, P., \u00c9va, T., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, FOCS \u201901, p. 329. IEEE Computer Society, Washington, DC, USA (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"916_CR46","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Sinclair, A.: Sherali\u2013Adams relaxations of the matching polytope. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC \u201909, pp. 293\u2013302. ACM, New York, NY, USA (2009)","DOI":"10.1145\/1536414.1536456"},{"key":"916_CR47","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC \u201997, pp. 475\u2013484. (1997)","DOI":"10.1145\/258533.258641"},{"key":"916_CR48","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 263\u2013272. (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"916_CR49","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovasz-Schrijver LP relaxations of Vertex Cover and Max Cut. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC \u201907, pp. 302\u2013310. ACM, New York, NY, USA (2007)","DOI":"10.1145\/1250790.1250836"},{"issue":"3","key":"916_CR50","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Disc. Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Disc. Math."},{"key":"916_CR51","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC \u201997. pp. 265\u2013274. (1997)","DOI":"10.1145\/258533.258600"},{"key":"916_CR52","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Santa Claus schedules jobs on unrelated machines. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 617\u2013626. ACM, New York, NY, USA, (2011)","DOI":"10.1145\/1993636.1993718"},{"key":"916_CR53","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: Lov\u00e1sz-Schrijver reformulation. In: Cochran, J.J., Anthony Cox, Jr. L., Keskinocak, P., Kharoufeh, J.P., Smith, J.C. (eds.) Encyclopedia of Operations Research and Management Science. Wiley, New Jersey (2011)","DOI":"10.1002\/9780470400531.eorms0479"},{"key":"916_CR54","unstructured":"Vygen, J.: Approximation Algorithms for Facility Location Problems (Lecture Notes). Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, (2005). URL: www.or.uni-bonn.de\/vygen\/files\/fl.pdf"},{"key":"916_CR55","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms, 1st edn. Cambridge University Press, New York (2011)","edition":"1"},{"issue":"3","key":"916_CR56","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"916_CR57","doi-asserted-by":"crossref","unstructured":"Zhang, J., Chen, B., Ye, Y.: A multi-exchange local search algorithm for the capacitated facility location problem. In: Proceedings of the 10th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 219\u2013233, (2004)","DOI":"10.1007\/978-3-540-25960-2_17"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0916-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0916-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0916-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T04:58:59Z","timestamp":1748408339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0916-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,31]]},"references-count":57,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["916"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0916-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2015,5,31]]}}}