{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T18:29:45Z","timestamp":1764872985686},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"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,4]]},"DOI":"10.1007\/s00453-007-9005-x","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T18:28:25Z","timestamp":1190917705000},"page":"455-478","source":"Crossref","is-referenced-by-count":29,"title":["Incremental Medians via Online Bidding"],"prefix":"10.1007","volume":"50","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Kenyon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Noga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9005_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Rajagopalan, R., Shmoys, D.B.: Lagrangian relaxation for the k-median problem: new insights and continuity properties. In: Proc. 11th European Symp. on Algorithms (ESA), pp.\u00a031\u201342 (2003)","DOI":"10.1007\/978-3-540-39658-1_6"},{"key":"9005_CR2","first-page":"21","volume-title":"Proc. 33rd Symp. Theory of Computing (STOC)","author":"V. Arya","year":"2001","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proc. 33rd Symp. Theory of Computing (STOC), pp.\u00a021\u201329. ACM, New York (2001)"},{"issue":"3","key":"9005_CR3","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"9005_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: Proc. 46th Symp. Foundations of Computer Science (FOCS), pp.\u00a0293\u2013304 (2006)","DOI":"10.1109\/FOCS.2006.39"},{"key":"9005_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarti, S., Phillips, C.A., Schulz, A.S., Shmoys, D.B., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: Automata, Languages and Programming, pp.\u00a0646\u2013657 (1996)","DOI":"10.1007\/3-540-61440-0_166"},{"key":"9005_CR6","first-page":"626","volume-title":"Proc. 29th Symp. Theory of Computing (STOC)","author":"M. Charikar","year":"1997","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. In: Proc. 29th Symp. Theory of Computing (STOC), pp.\u00a0626\u2013635. ACM, New York (1997)"},{"key":"9005_CR7","first-page":"378","volume-title":"Proc. 40th Symp. Foundations of Computer Science (FOCS)","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proc. 40th Symp. Foundations of Computer Science (FOCS), pp.\u00a0378\u2013388. IEEE, New York (1999)"},{"issue":"4","key":"9005_CR8","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(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"9005_CR9","first-page":"1","volume-title":"Proc. 31st Symp. Theory of Computing (STOC)","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Guha, S., Tardos, E., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proc. 31st Symp. Theory of Computing (STOC), pp.\u00a01\u201310. ACM, New York (1999)"},{"key":"9005_CR10","first-page":"363","volume-title":"Proc. 36th Symp. Theory of Computing (STOC)","author":"C. Chekuri","year":"2004","unstructured":"Chekuri, C., Goel, A., Khanna, S., Kumar, A.: Multi-processor scheduling to minimize flow time with \u03b5-resource augmentation. In: Proc. 36th Symp. Theory of Computing (STOC), pp.\u00a0363\u2013372. ACM, New York (2004)"},{"key":"9005_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/11682462_31","volume-title":"Proc. 7th Latin American Theoretical Informatics Symp. (LATIN)","author":"M. Chrobak","year":"2006","unstructured":"Chrobak, M., Kenyon, C., Noga, J., Young, N.: Online medians via online bidding. In: Proc. 7th Latin American Theoretical Informatics Symp. (LATIN). Lecture Notes in Computer Science, vol.\u00a03887, pp.\u00a0311\u2013322. Springer, Berlin (2006)"},{"key":"9005_CR12","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2005.09.009","volume":"97","author":"M. Chrobak","year":"2006","unstructured":"Chrobak, M., Kenyon, C., Young, N.E.: The reverse greedy algorithm for the k-median problem. Inf. Process. Lett. 97, 68\u201372 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9005_CR13","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/j.jcss.2004.10.006","volume":"70","author":"S. Dasgupta","year":"2005","unstructured":"Dasgupta, S., Long, P.M.: Performance guarantees for hierarchical clustering. J. Comput. Syst. Sci. 70(4), 555\u2013569 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"9005_CR14","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1023\/A:1008023416823","volume":"30","author":"R. Fagin","year":"1998","unstructured":"Fagin, R., Stockmeyer, L.: Relaxing the triangle inequality in pattern matching. Int. J. Comput. Vis. 30, 219\u2013231 (1998)","journal-title":"Int. J. Comput. Vis."},{"key":"9005_CR15","first-page":"152","volume-title":"Proc. 7th Symp. on Discrete Algorithms (SODA)","author":"M. Goemans","year":"1996","unstructured":"Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. In: Proc. 7th Symp. on Discrete Algorithms (SODA), pp.\u00a0152\u2013158. ACM\/SIAM, New York (1996)"},{"issue":"1","key":"9005_CR16","first-page":"111","volume":"82","author":"M. Goemans","year":"1998","unstructured":"Goemans, M., Kleinberg, J.: An improved approximation ratio for the minimum latency problem. Math. Program. 82(1), 111\u2013124 (1998)","journal-title":"Math. Program."},{"key":"9005_CR17","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":"9005_CR18","first-page":"731","volume-title":"Proc. 34th Symp. Theory of Computing (STOC)","author":"K. Jain","year":"2002","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proc. 34th Symp. Theory of Computing (STOC), pp.\u00a0731\u2013740. ACM, New York (2002)"},{"key":"9005_CR19","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-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"9005_CR20","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/347476.347479","volume":"47","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47, 214\u2013221 (2000)","journal-title":"J. ACM"},{"issue":"1","key":"9005_CR21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M.-Y. Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201380 (1996). Preliminary version appeared in the Proceedings of the Symp. on Discrete Algorithms, Austin, TX, January 1993","journal-title":"Inf. Comput."},{"key":"9005_CR22","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M.R. Korupolu","year":"2000","unstructured":"Korupolu, M.R., Greg Plaxton, C., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"9005_CR23","first-page":"444","volume-title":"Proc. 40th Symp. Foundations of Computer Science (FOCS)","author":"E. Koutsoupias","year":"1999","unstructured":"Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proc. 40th Symp. Foundations of Computer Science (FOCS), pp.\u00a0444\u2013449. IEEE, New York (1999)"},{"key":"9005_CR24","volume-title":"Proc. 17th Symp. on Discrete Algorithms (SODA)","author":"G. Lin","year":"2006","unstructured":"Lin, G., Nagarajan, C., Rajamaran, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: Proc. 17th Symp. on Discrete Algorithms (SODA). ACM\/SIAM, New York (2006)"},{"key":"9005_CR25","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J.-H. Lin","year":"1992","unstructured":"Lin, J.-H., Vitter, J.S.: Approximation algorithms for geometric median problems. Inf. Process. Lett. 44, 245\u2013249 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9005_CR26","first-page":"771","volume-title":"Proc. 24th Symp. Theory of Computing (STOC)","author":"J.-H. Lin","year":"1992","unstructured":"Lin, J.-H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation (extended abstract). In: Proc. 24th Symp. Theory of Computing (STOC), pp.\u00a0771\u2013782. ACM, New York (1992)"},{"key":"9005_CR27","first-page":"339","volume-title":"Proc. 41st Symp. Foundations of Computer Science (FOCS)","author":"R.R. Mettu","year":"2000","unstructured":"Mettu, R.R., Greg Plaxton, C.: The online median problem. In: Proc. 41st Symp. Foundations of Computer Science (FOCS), pp.\u00a0339\u2013348. IEEE, New York (2000)"},{"key":"9005_CR28","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R.R. Mettu","year":"2003","unstructured":"Mettu, R.R., Greg Plaxton, C.: The online median problem. SIAM J. Comput. 32, 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9005_CR29","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R. Motwani","year":"1994","unstructured":"Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor. Comput. Sci. 130(1), 17\u201347 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9005_CR30","first-page":"86","volume-title":"Proc. 11th Symp. on Discrete Algorithms (SODA)","author":"N.E. Young","year":"2000","unstructured":"Young, N.E.: K-medians, facility location, and the Chernoff\u2013Wald bound. In: Proc. 11th Symp. on Discrete Algorithms (SODA), pp.\u00a086\u201395. ACM\/SIAM, New York (2000)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9005-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9005-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9005-x","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-9005-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["9005"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9005-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}