{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:18Z","timestamp":1759063578563},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,11,1]],"date-time":"2014-11-01T00:00:00Z","timestamp":1414800000000},"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":["J Glob Optim"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s10898-014-0251-6","type":"journal-article","created":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T09:21:58Z","timestamp":1415006518000},"page":"483-496","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Combinatorial approximation algorithms for the robust facility location problem with penalties"],"prefix":"10.1007","volume":"64","author":[{"given":"Fengmin","family":"Wang","sequence":"first","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,1]]},"reference":[{"key":"251_CR1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2003","unstructured":"Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the $$k$$ k -level facility location problem. SIAM J. Discrete Math. 18, 207\u2013217 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"251_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Anand, L., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A $$3$$ 3 -approximation for facility location with uniform capacities. In: Proceedings of IPCO, pp. 149\u2013162 (2010)","DOI":"10.1007\/978-3-642-13036-6_12"},{"key":"251_CR3","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0167-6377(01)00087-6","volume":"29","author":"A Bumb","year":"2001","unstructured":"Bumb, A.: An approximation algorithm for the maximization version of the two level uncapacitated facility location problem. Oper. Res. Lett. 29, 155\u2013161 (2001)","journal-title":"Oper. Res. Lett."},{"key":"251_CR4","doi-asserted-by":"crossref","unstructured":"Byrka, J., Srinivasan, A., Swamy, C.: Fault-tolerant facility location: a randomized dependent LP-rounding algorithm. In: Proceedings of IPCO, pp. 244\u2013257 (2010)","DOI":"10.1007\/978-3-642-13036-6_19"},{"key":"251_CR5","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"251_CR6","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Naraasimban, G.: Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp. 642\u2013651 (2001)"},{"key":"251_CR7","unstructured":"Chechik, S., Peleg, D.: Robust fault-tolerant facility location. In: Proceedings of STACS, pp. 191\u2013202 (2010)"},{"key":"251_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-007-9032-7","volume":"53","author":"X Chen","year":"2007","unstructured":"Chen, X., Chen, B.: Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53, 263\u2013297 (2007)","journal-title":"Algorithmica"},{"key":"251_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"251_CR10","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, 207\u2013222 (2005)","journal-title":"Math. Program."},{"key":"251_CR11","unstructured":"Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Mirchandani, P.B., Francis, R.L. (eds.) Discrete Location Theory, pp. 119\u2013171 (1990)"},{"key":"251_CR12","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du, D., Lu, R., Xu, D.: A primal\u2013dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191\u2013200 (2012)","journal-title":"Algorithmica"},{"key":"251_CR13","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Rothvo $$\\beta $$ \u03b2 , T.: Approximation algorithm for single and connected facility location. In: Proceedings of IPCO, pp. 248\u2013260 (2011)","DOI":"10.1007\/978-3-642-20807-2_20"},{"key":"251_CR14","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. Algorithm 31, 228\u2013248 (1999)","journal-title":"J. Algorithm"},{"key":"251_CR15","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1002\/net.10080","volume":"42","author":"M Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Networks 42, 42\u201347 (2003)","journal-title":"Networks"},{"key":"251_CR16","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, 795\u2013824 (2003)","journal-title":"J. ACM."},{"key":"251_CR17","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$$ k -median problems using the primal\u2013dual schema and Lagrangian relaxation. J. ACM. 48, 274\u2013296 (2001)","journal-title":"J. ACM."},{"key":"251_CR18","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/s10878-009-9227-8","volume":"18","author":"H Jung","year":"2009","unstructured":"Jung, H., Hasan, M.K., Chwa, K.-Y.: A $$6.55$$ 6.55 factor primal\u2013dual approximation algorithm for the connected facility location problem. J. Comb. Optim. 18, 258\u2013271 (2009)","journal-title":"J. Comb. Optim."},{"key":"251_CR19","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manag. Sci. 9, 643\u2013666 (1963)","journal-title":"Manag. Sci."},{"key":"251_CR20","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10107-010-0380-8","volume":"131","author":"R Levi","year":"2012","unstructured":"Levi, R., Shmoys, D.B., Swamy, C.: LP-based approximation algorithms for capacitated facility location. Math. Program. 131, 365\u2013379 (2012)","journal-title":"Math. Program."},{"key":"251_CR21","doi-asserted-by":"crossref","unstructured":"Li, S.: A $$1.488$$ 1.488 -approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, Part II, pp. 77\u201388 (2011)","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"251_CR22","doi-asserted-by":"crossref","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear\/submodular penalty. In: Proceedings of COCOON, pp. 292\u2013303 (2013)","DOI":"10.1007\/978-3-642-38768-5_27"},{"key":"251_CR23","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1007\/s10898-012-9852-0","volume":"56","author":"G Li","year":"2013","unstructured":"Li, G., Li, Y., Shu, J., Xu, D.: A cross-monotonic cost sharing scheme for the concave facility location game. J. Global Optim. 56, 1325\u20131335 (2013)","journal-title":"J. Global Optim."},{"key":"251_CR24","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.ipl.2012.02.004","volume":"112","author":"Y Li","year":"2012","unstructured":"Li, Y., Xu, D., Du, D., Xiu, N.: Improved approximation algorithms for the robust fault-tolerant facility location problem. Inform. Process. Lett. 112, 361\u2013364 (2012)","journal-title":"Inform. Process. Lett."},{"key":"251_CR25","doi-asserted-by":"crossref","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Proceedings of ESA, pp. 409\u2013421 (2003)","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"251_CR26","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of APPROX, pp. 229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"key":"251_CR27","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A $$2$$ 2 -approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of APPROX, pp. 129\u2013140 (2003)","DOI":"10.1007\/978-3-540-45198-3_12"},{"key":"251_CR28","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tard\u00f6s, E., Wexler, T.: Facility location with hard capacities. In: Proceedings of FOCS, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"251_CR29","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1002\/net.20315","volume":"55","author":"HE Romeijn","year":"2010","unstructured":"Romeijn, H.E., Sharkey, T.C., Max Shen, Z.-J., Zhang, J.: Integrating facility location and production planning decisions. Networks 55, 78\u201389 (2010)","journal-title":"Networks"},{"key":"251_CR30","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tard\u00f6s, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of STOC, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"251_CR31","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1287\/trsc.1090.0302","volume":"44","author":"J Shu","year":"2010","unstructured":"Shu, J.: An efficient greedy heuristic for warehouse-retailer network design optimization. Transp. Sci. 44, 183\u2013192 (2010)","journal-title":"Transp. Sci."},{"key":"251_CR32","doi-asserted-by":"crossref","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of IPCO, pp. 240\u2013257 (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"key":"251_CR33","volume-title":"Approximation Algorithm","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithm. Springer, New York (2001)"},{"key":"251_CR34","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. Cambridge University Press, Cambridge (2011)"},{"key":"251_CR35","doi-asserted-by":"crossref","first-page":"2530","DOI":"10.1007\/s11425-009-0173-9","volume":"52","author":"D Xu","year":"2009","unstructured":"Xu, D.: A cross-monotonic cost sharing method for the facility location game with service installation costs. Sci. China Ser. A. 52, 2530\u20132536 (2009)","journal-title":"Sci. China Ser. A."},{"key":"251_CR36","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.orl.2005.06.002","volume":"34","author":"D Xu","year":"2006","unstructured":"Xu, D., Du, D.: The $$k$$ k -level facility location game. Oper. Res. Lett. 34, 421\u2013426 (2006)","journal-title":"Oper. Res. Lett."},{"key":"251_CR37","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.ipl.2005.01.005","volume":"94","author":"G Xu","year":"2005","unstructured":"Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Inform. Process. Lett. 94, 119\u2013123 (2005)","journal-title":"Inform. Process. Lett."},{"key":"251_CR38","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/s10878-007-9127-8","volume":"17","author":"G Xu","year":"2008","unstructured":"Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424\u2013436 (2008)","journal-title":"J. Comb. Optim."},{"key":"251_CR39","doi-asserted-by":"crossref","unstructured":"Ye, Y., Zhang, J.: An approximation algorithm for the dynamic facility location problem. In: Combinatorial Optimization in Communication Networks, Kluwer Academic Publishers, pp. 623\u2013637 (2005)","DOI":"10.1007\/0-387-29026-5_22"},{"key":"251_CR40","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10107-006-0704-x","volume":"108","author":"J Zhang","year":"2006","unstructured":"Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159\u2013176 (2006)","journal-title":"Math. Program."},{"key":"251_CR41","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang, P.: A new approximation algorithm for the $$k$$ k -facility location problem. Theor. Comput. Sci. 384, 126\u2013135 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"251_CR42","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 389\u2013403 (2005)","journal-title":"Math. Oper. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-014-0251-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-014-0251-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-014-0251-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T10:44:40Z","timestamp":1598438680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-014-0251-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,1]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["251"],"URL":"https:\/\/doi.org\/10.1007\/s10898-014-0251-6","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,1]]}}}