{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:55Z","timestamp":1740122455310,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,8,12]],"date-time":"2016-08-12T00:00:00Z","timestamp":1470960000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2013\/21744-8"],"award-info":[{"award-number":["2013\/21744-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s10878-016-0064-2","type":"journal-article","created":{"date-parts":[[2016,8,12]],"date-time":"2016-08-12T11:45:46Z","timestamp":1471002346000},"page":"266-278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation algorithms for k-level stochastic facility location problems"],"prefix":"10.1007","volume":"34","author":[{"given":"Lucas P.","family":"Melo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fl\u00e1vio K.","family":"Miyazawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lehilton L. C.","family":"Pedrosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael C. S.","family":"Schouery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,12]]},"reference":[{"issue":"5\u20136","key":"64_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"K Aardal","year":"1999","unstructured":"Aardal K, Chudak FA, Shmoys DB (1999) A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform Process Lett 72(5\u20136):161\u2013167","journal-title":"Inform Process Lett"},{"issue":"5","key":"64_CR2","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0167-6377(02)00162-1","volume":"30","author":"AA Ageev","year":"2002","unstructured":"Ageev AA (2002) Improved approximation algorithms for multilevel facility location problems. Oper Res Lett 30(5):327\u2013332","journal-title":"Oper Res Lett"},{"key":"64_CR3","doi-asserted-by":"crossref","unstructured":"Ageev AA, Ye Y, Zhang J (2003) Improved combinatorial approximation algorithms for the k-level facility location problem. In: Proc. 30th Int. Colloquium on Automata, Languages and Programming, pp 145\u2013156","DOI":"10.1007\/3-540-45061-0_13"},{"key":"64_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"EML Beale","year":"1955","unstructured":"Beale EML (1955) On minimizing a convex function subject to linear inequalities. J R Stat Soc Ser B 17:173\u2013184","journal-title":"J R Stat Soc Ser B"},{"issue":"6","key":"64_CR5","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka J, Aardal K (2010) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput 39(6):2212\u20132231","journal-title":"SIAM J Comput"},{"issue":"1","key":"64_CR6","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00224-014-9575-3","volume":"58","author":"J Byrka","year":"2016","unstructured":"Byrka J, Li S, Rybicki B (2016) Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties). Theory Comput Syst 58(1):19\u201344","journal-title":"Theory Comput Syst"},{"key":"64_CR7","doi-asserted-by":"crossref","unstructured":"Byrka J, Rybicki B (2012) Improved LP-rounding approximation algorithm for k-level uncapacitated facility location. In: Proc. 39th Int. Colloquium on Automata, Languages, and Programming, pp 157\u2013169","DOI":"10.1007\/978-3-642-31594-7_14"},{"issue":"1","key":"64_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33(1):1\u201325","journal-title":"SIAM J Comput"},{"key":"64_CR9","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","volume":"1","author":"GB Dantzig","year":"1955","unstructured":"Dantzig GB (1955) Linear programming under uncertainty. Manage Sci 1:197\u2013206","journal-title":"Manage Sci"},{"key":"64_CR10","doi-asserted-by":"crossref","unstructured":"Dye S, Stougie L, Tomasgard A (1999) The stochastic single resourceservice-provision problem. Naval Res Logist 50(8):869\u2013887 (2003). Also appeared as \u201cThe stochastic single nodeservice provision problem\u201d, COSOR-Memorandum 99-13, Dept. ofMathematics and Computer Science, Eindhoven Technical University, Eindhoven","DOI":"10.1002\/nav.10092"},{"issue":"1","key":"64_CR11","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 (1999) Greedy strikes back: improved facility location algorithms. Jf Algorithms 31(1):228\u2013248","journal-title":"Jf Algorithms"},{"key":"64_CR12","unstructured":"INFORMS: Section on Location Analysis (2015). https:\/\/www.informs.org\/Community\/SOLA"},{"key":"64_CR13","doi-asserted-by":"crossref","unstructured":"Krishnaswamy R, Sviridenko M (2012) Inapproximability of the multi-level uncapacitated facility location problem. In: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp 718\u2013734","DOI":"10.1137\/1.9781611973099.59"},{"key":"64_CR14","unstructured":"Mahdian M (2004) Facility location and the analysis of algorithms through factor-revealing programs. Ph.D. thesis, Massachusetts Institute of Technology"},{"key":"64_CR15","doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proc. 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization, pp 229\u2013242","DOI":"10.1007\/3-540-45753-4_20"},{"issue":"1","key":"64_CR16","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravi","year":"2006","unstructured":"Ravi R, Sinha A (2006) Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math Program 108(1):97\u2013114","journal-title":"Math Program"},{"key":"64_CR17","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: Proc. 29th Annual ACM Symposium on the Theory of Computing, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"64_CR18","unstructured":"Srinivasan A (2007) Approximation algorithms for stochastic and risk-averse optimization. In: Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1305\u20131313"},{"issue":"1","key":"64_CR19","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1122480.1122493","volume":"37","author":"C Swamy","year":"2006","unstructured":"Swamy C, Shmoys DB (2006) Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1):33\u201346","journal-title":"SIGACT News"},{"issue":"5","key":"64_CR20","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1016\/j.orl.2010.04.010","volume":"38","author":"Z Wang","year":"2010","unstructured":"Wang Z, Du D, Gabor AF, Xu D (2010) An approximation algorithm for the k-level stochastic facility location problem. Oper Res Lett 38(5):386\u2013389","journal-title":"Oper Res Lett"},{"key":"64_CR21","unstructured":"Wang Z, Du D, Gabor AF, Xu, D (2011) Erratum to: \u201cAn approximation algorithm for the k-level stochastic facility location problem\u201d [Oper. Res. Lett. 38(2010) 386\u2013389]. Oper Res Lett 39(2):160\u2013161"},{"key":"64_CR22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-14355-7_26","volume-title":"Algorithmic aspects in information and management, LNCS","author":"Z Wang","year":"2010","unstructured":"Wang Z, Du D, Xu D (2010) A primal-dual approximation algorithm for the k-level stochastic facility location problem. In: Chen B (ed) Algorithmic aspects in information and management, LNCS, vol 6124. Springer, Berlin Heidelberg, pp 253\u2013260"},{"key":"64_CR23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2014.09.045","volume":"562","author":"C Wu","year":"2015","unstructured":"Wu C, Du D, Xu D (2015) Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach. Theor Comput Sci 562:213\u2013226","journal-title":"Theor Comput Sci"},{"key":"64_CR24","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1007\/0-387-29026-5_22","volume-title":"Combinatorial optimization in communication networks, combinatorial optimization","author":"Y Ye","year":"2006","unstructured":"Ye Y, Zhang J (2006) An approximation algorithm for the dynamic facility location problem. In: Cheng M, Li Y, Du DZ (eds) Combinatorial optimization in communication networks, combinatorial optimization, vol 18. Springer, US, pp 623\u2013637"},{"issue":"1","key":"64_CR25","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10107-006-0704-x","volume":"108","author":"J Zhang","year":"2006","unstructured":"Zhang J (2006) Approximating the two-level facility location problem via a quasi-greedy approach. Math Program 108(1):159\u2013176","journal-title":"Math Program"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0064-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0064-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0064-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0064-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T21:15:20Z","timestamp":1718745320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0064-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,12]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["64"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0064-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2016,8,12]]}}}