{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:08Z","timestamp":1759638308456},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,9,30]],"date-time":"2014-09-30T00:00:00Z","timestamp":1412035200000},"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":[[2015,11]]},"DOI":"10.1007\/s10107-014-0821-x","type":"journal-article","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T11:30:49Z","timestamp":1411990249000},"page":"655-685","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems"],"prefix":"10.1007","volume":"153","author":[{"given":"Cristina G.","family":"Fernandes","sequence":"first","affiliation":[]},{"given":"Luis A. A.","family":"Meira","sequence":"additional","affiliation":[]},{"given":"Fl\u00e1vio K.","family":"Miyazawa","sequence":"additional","affiliation":[]},{"given":"Lehilton L. C.","family":"Pedrosa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,30]]},"reference":[{"key":"821_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean $$k$$ k -medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"821_CR2","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"821_CR3","unstructured":"Byrka, J., Ghodsi, M., Srinivasan, A.: LP-Rounding Algorithms for Facility-Location Problems (2010). http:\/\/arxiv.org\/abs\/1007.3611"},{"key":"821_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the $$k$$ k -median problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"821_CR5","doi-asserted-by":"crossref","unstructured":"Chudak, F., Shmoys, D.: Improved approximation algorithms for the capacitated facility location problem. In: Proceedings 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 875\u2013876 (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"issue":"1","key":"821_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F Chudak","year":"2004","unstructured":"Chudak, F., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1\u201325 (2004)","journal-title":"SIAM J. Comput."},{"key":"821_CR7","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceedings of the 9th Annual ACM-SIAM Sympsoium on Discrete Algorithms, pp. 649\u2013657 (1998)"},{"issue":"1","key":"821_CR8","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(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"821_CR9","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D Hochbaum","year":"1982","unstructured":"Hochbaum, D.: Heuristics for the fixed cost median problem. Math. Program. 22(2), 148\u2013162 (1982)","journal-title":"Math. Program."},{"issue":"6","key":"821_CR10","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.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"key":"821_CR11","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"821_CR12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and $$k$$ k -Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"821_CR13","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":"821_CR14","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"2","key":"821_CR15","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":"821_CR16","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"821_CR17","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274. ACM (1997)","DOI":"10.1145\/258533.258600"},{"key":"821_CR18","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-47867-1_18","volume-title":"Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science","author":"M Sviridenko","year":"2002","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Cook, W.J., Schulz, A.S. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 2337, pp. 240\u2013257. Springer, Berlin (2002)"},{"key":"821_CR19","unstructured":"Vygen, J.: Approximation Algorithms for Facility Location Problems (Lecture Notes). Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0821-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0821-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0821-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,15]],"date-time":"2019-08-15T11:00:17Z","timestamp":1565866817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0821-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,30]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["821"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0821-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,30]]}}}