{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:17:50Z","timestamp":1787386670207,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540742074","type":"print"},{"value":"9783540742081","type":"electronic"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_3","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"29-43","source":"Crossref","is-referenced-by-count":55,"title":["An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Aardal, K., Chudak, F., Shmoys, D.B.: A 3-approximation algorithm for the k-level uncapacitated facility location problem Information Processing Letters. 72, 161\u2013167 (1999)","DOI":"10.1016\/S0020-0190(99)00144-1"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-45061-0_13","volume-title":"Automata, Languages and Programming","author":"A. Ageev","year":"2003","unstructured":"Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial Approximation algorithms for the k-level facility location problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 145\u2013156. Springer, Heidelberg (2003)"},{"issue":"3","key":"3_CR3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.orl.2006.03.017","volume":"35","author":"J. Byrka","year":"2007","unstructured":"Byrka, J., Aardal, K.: The approximation gap for the metric facility location problem is not yet closed. Operations Research Letters (ORL)\u00a035(3), 379\u2013384 (2007)","journal-title":"Operations Research Letters (ORL)"},{"key":"3_CR4","first-page":"378","volume-title":"FOCS","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: FOCS. Proc. of the 40th IEEE Symp. on Foundations of Computer Science, pp. 378\u2013388. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Chudak, F.A.: Improved approximation algorithms for uncapacitated facility location. In: Proc. of the 6th Integer Programing and Combinatorial Optimization (IPCO), pp. 180\u2013194 (1998)","DOI":"10.1007\/3-540-69346-7_14"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F.A. Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput.\u00a033(1), 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"8","author":"G. Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Science\u00a08, 789\u2013810 (1977)","journal-title":"Management Science"},{"key":"3_CR8","first-page":"228","volume-title":"SODA","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: SODA. Proc. of the 9th ACM-SIAM Symp. on Discrete Algorithms, pp. 228\u2013248. ACM Press, New York (1998)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Heuristics for the fixed cost median problem. Mathematical Programming\u00a022, 148\u2013162 (1982)","journal-title":"Mathematical Programming"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1145\/509907.510012","volume-title":"STOC","author":"K. Jain","year":"2002","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC. Proc. of the 34th ACM Symp. on Theory of Computing, pp. 731\u2013740. ACM Press, New York (2002)"},{"key":"3_CR11","first-page":"771","volume-title":"STOC","author":"J.-H. Lin","year":"1992","unstructured":"Lin, J.-H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation. In: STOC. Proc. of the 24th ACM Symp. on Theory of Computing, pp. 771\u2013782. ACM Press, New York (1992)"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 229\u2013242. Springer, Heidelberg (2002)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.B. Shmoys","year":"2000","unstructured":"Shmoys, D.B.: Approximation algorithms for facility location problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 265\u2013274. Springer, Heidelberg (2000)"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/258533.258600","volume-title":"STOC","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: STOC. Proc. of the 29th ACM Symp. on Theory of Computing, pp. 265\u2013274. ACM Press, New York (1997)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proc. of the 9th Integer Programming and Combinatorial Optimization (IPCO), pp. 240\u2013257 (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"key":"3_CR16","unstructured":"Vygen, J.: Approximation algorithms for facility location problems (Lecture Notes), Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn(2005), http:\/\/www.or.uni-bonn.de\/~vygen\/fl.pdf"},{"key":"3_CR17","doi-asserted-by":"publisher","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. Mathematical Programming, Ser. A\u00a0108, 159\u2013176 (2006)","journal-title":"Mathematical Programming, Ser. A"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T22:47:24Z","timestamp":1684018044000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}