{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T05:17:33Z","timestamp":1772860653158,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,24]],"date-time":"2007-10-24T00:00:00Z","timestamp":1193184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1007\/s00453-007-9049-y","type":"journal-article","created":{"date-parts":[[2007,10,23]],"date-time":"2007-10-23T14:40:32Z","timestamp":1193150432000},"page":"1-57","source":"Crossref","is-referenced-by-count":49,"title":["On the Competitive Ratio for Online Facility Location"],"prefix":"10.1007","volume":"50","author":[{"given":"Dimitris","family":"Fotakis","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,24]]},"reference":[{"issue":"1","key":"9049_CR1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1006\/jagm.1997.0906","volume":"27","author":"S. Albers","year":"1998","unstructured":"Albers, S., Koga, H.: New online algorithms for the page replication problem. J.\u00a0Algorithms 27(1), 75\u201396 (1998)","journal-title":"J.\u00a0Algorithms"},{"key":"9049_CR2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.ic.2004.06.002","volume":"194","author":"A. Anagnostopoulos","year":"2004","unstructured":"Anagnostopoulos, A., Bent, R., Upfal, E., Van Hentenryck, P.: A\u00a0simple and deterministic competitive algorithm for online facility location. Inf. Comput. 194, 175\u2013202 (2004)","journal-title":"Inf. Comput."},{"key":"9049_CR3","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. In: Proc. of the 33rd ACM Symp. on Theory of Computing (STOC \u201901), pp.\u00a021\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"9049_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Bartal, Y., Fiat, A.: Competitive distributed file allocation. In: Proc. of the 25th ACM Symp. on Theory of Computing (STOC \u201993), pp.\u00a0164\u2013173 (1993)","DOI":"10.1145\/167088.167142"},{"key":"9049_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proc. of the 37th IEEE Symp. on Foundations of Computer Science (FOCS \u201996), pp.\u00a0184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"issue":"3","key":"9049_CR6","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1006\/jcss.1995.1073","volume":"51","author":"Y. Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Rabani, Y.: Competitive algorithms for distributed data management. J.\u00a0Comput. Syst. Sci. 51(3), 341\u2013358 (1995)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9049_CR7","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"9049_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. In: Proc. of the 29th ACM Symp. on Theory of Computing (STOC \u201997), pp.\u00a0626\u2013635 (1997)","DOI":"10.1145\/258533.258657"},{"key":"9049_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proc. of the 40th IEEE Symp. on Foundations of Computer Science (FOCS \u201999), pp.\u00a0378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"9049_CR10","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proc. of the 35th ACM Symp. on Theory of Computing (STOC \u201903), pp.\u00a030\u201339 (2003)","DOI":"10.1145\/780542.780548"},{"key":"9049_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/3-540-44436-X_15","volume-title":"Proc. of APPROX \u201900","author":"R. Fleischer","year":"2000","unstructured":"Fleischer, R., Seiden, S.: New results for online page replication. In: Proc. of APPROX \u201900. Lecture Notes in Computer Science, vol. 1913, pp. 144\u2013154. Springer, Berlin (2000)"},{"key":"9049_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/3-540-45061-0_51","volume-title":"Proc. of ICALP \u201903","author":"D. Fotakis","year":"2003","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. In: Proc. of ICALP \u201903. Lecture Notes in Computer Science, vol. 2719, pp. 637\u2013652. Springer, Berlin (2003)"},{"key":"9049_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-540-30140-0_32","volume-title":"Proc. of ESA \u201904","author":"D. Fotakis","year":"2004","unstructured":"Fotakis, D.: Incremental algorithms for facility location and k-median. In: Proc. of ESA \u201904. Lecture Notes in Computer Science, vol. 3221, pp. 347\u2013358. Springer, Berlin (2004)"},{"key":"9049_CR14","unstructured":"Guha, S.: Approximation algorithms for facility location problems. PhD thesis, Stanford University (2000)"},{"key":"9049_CR15","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proc. of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA \u201998), pp.\u00a0649\u2013657 (1998)"},{"issue":"3","key":"9049_CR16","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M. Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discrete Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"9049_CR17","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proc. of the 34th ACM Symp. on Theory of Computing (STOC \u201902), pp.\u00a0731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"issue":"2","key":"9049_CR18","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-median problems using the primal-dual schema and Lagrangian relaxation. J.\u00a0Assoc. Comput. Mach. 48(2), 274\u2013296 (2001)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9049_CR19","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proc. of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA \u201998), pp.\u00a01\u201310 (1998)"},{"issue":"3","key":"9049_CR20","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1137\/S0097539795287824","volume":"28","author":"C. Lund","year":"1999","unstructured":"Lund, C., Reingold, N., Westbrook, J., Yan, D.: Competitive online algorithms for distributed data management. SIAM J. Comput. 28(3), 1086\u20131111 (1999)","journal-title":"SIAM J. Comput."},{"key":"9049_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Proc. of APPROX \u201902","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proc. of APPROX \u201902. Lecture Notes in Computer Science, vol. 2462, pp. 229\u2013242. Springer, Berlin (2002)"},{"issue":"3","key":"9049_CR22","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R.R. Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"key":"9049_CR23","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proc. of the 42nd IEEE Symp. on Foundations of Computer Science (FOCS \u201901), pp.\u00a0426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"9049_CR24","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Designing networks incrementally. In: Proc. of the 42nd IEEE Symp. on Foundations of Computer Science (FOCS \u201901), pp.\u00a0406\u2013415 (2001)","DOI":"10.1109\/SFCS.2001.959915"},{"key":"9049_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/3-540-44436-X_4","volume-title":"Proc. of APPROX \u201900","author":"D. Shmoys","year":"2000","unstructured":"Shmoys, D.: Approximation algorithms for facility location problems. In: Proc. of APPROX \u201900. Lecture Notes in Computer Science, vol. 1913, pp. 27\u201333. Springer, Berlin (2000)"},{"key":"9049_CR26","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proc. of the 29th ACM Symp. on Theory of Computing (STOC \u201997), pp.\u00a0265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"9049_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-47867-1_18","volume-title":"Proc. of IPCO \u201902","author":"M. Sviridenko","year":"2002","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proc. of IPCO \u201902. Lecture Notes in Computer Science, vol. 2337, pp. 240\u2013257. Springer, Berlin (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9049-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9049-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9049-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:44:59Z","timestamp":1559137499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9049-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,24]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["9049"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9049-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,24]]}}}