{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T05:11:34Z","timestamp":1718946694777},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,3,3]],"date-time":"2009-03-03T00:00:00Z","timestamp":1236038400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s10878-009-9219-8","type":"journal-article","created":{"date-parts":[[2009,3,2]],"date-time":"2009-03-02T13:49:25Z","timestamp":1236001765000},"page":"307-320","source":"Crossref","is-referenced-by-count":3,"title":["Incremental Facility Location Problem and\u00a0Its\u00a0Competitive Algorithms"],"prefix":"10.1007","volume":"20","author":[{"given":"Wenqiang","family":"Dai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianju","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,3,3]]},"reference":[{"issue":"4","key":"9219_CR1","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"PK Agarwal","year":"1998","unstructured":"Agarwal PK, Sharir M (1998) Efficient algorithms for geometric optimization. ACM Comput Surv 30(4):412\u2013458","journal-title":"ACM Comput Surv"},{"key":"9219_CR2","doi-asserted-by":"crossref","unstructured":"Arora S, Raghavan P, Rao S (1998) Approximation schemes for Euclidean k-medians and related problems. In: Proc 30th annual ACM symposium on theory of computing (STOC\u201998), pp 106\u2013113","DOI":"10.1145\/276698.276718"},{"key":"9219_CR3","doi-asserted-by":"crossref","unstructured":"Arya V, Garg N, Khandekar R, Munagala K, Pandit V (2001) Local search heuristics for k-median and facility location problems. In: STOC\u201901, pp 21\u201329","DOI":"10.1145\/380752.380755"},{"key":"9219_CR4","doi-asserted-by":"crossref","unstructured":"Byrka J (2007) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: APPROX-RANDOM, pp 29\u201343","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"9219_CR5","doi-asserted-by":"crossref","unstructured":"Charikar M, Guha S (1999) Improved combinatorial algorithms for facility location and k-median problems. In: Proc FOCS\u201999, pp 378\u2013388","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"9219_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 (1997) Incremental clustering and dynamic information retrieval. In: Proc 29th symp theory of computing (STOC). ACM, New York, pp 626\u2013635"},{"key":"9219_CR7","series-title":"LNCS","first-page":"207","volume-title":"WAOA07","author":"M Chrobak","year":"2008","unstructured":"Chrobak M, Hurand M (2008) Better bound for incremental medians. In: WAOA07. LNCS, vol 4927. Springer, Berlin, pp 207\u2013217"},{"key":"9219_CR8","series-title":"LNCS","first-page":"455","volume-title":"Proceedings of Latin American theoretical informatics (LATIN06)","author":"M Chrobak","year":"2006","unstructured":"Chrobak M, Kenyon C, Young NE (2006a) Oblivious medians via online bidding. In: Proceedings of Latin American theoretical informatics (LATIN06). LNCS, vol 3887. Springer, Berlin, pp 455\u2013478. Also in Algorithmica 50 (2008)"},{"key":"9219_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/3-540-69346-7_14","volume-title":"Proc 5th conference on integer programming and combinatorial optimization","author":"F Chudak","year":"1998","unstructured":"Chudak F (1998) Improved algorithms for uncapacitated facility location problem. In: Proc 5th conference on integer programming and combinatorial optimization. LNCS, vol 1412. Springer, Berlin, pp 180\u2013194"},{"key":"9219_CR10","doi-asserted-by":"crossref","unstructured":"Chudak F, Shmoys DB (1999) Improved approximation algorithms for capacitated facility location problem. In: Proc 10th ACM-SIAM symposium on discrete algorithms","DOI":"10.1007\/3-540-48777-8_8"},{"key":"9219_CR11","series-title":"LNCS","first-page":"637","volume-title":"Proc of ICALP\u201903","author":"D Fotakis","year":"2003","unstructured":"Fotakis D (2003) On the competitive ratio for online facility location. In: Proc of ICALP\u201903. LNCS, vol\u00a02719. Springer, Berlin, pp 637\u2013652"},{"issue":"1","key":"9219_CR12","first-page":"111","volume":"82","author":"M Goemans","year":"1998","unstructured":"Goemans M, Kleinberg J (1998) An improved approximation ratio for the minimum latency problem. Math Program 82(1):111\u2013124","journal-title":"Math Program"},{"key":"9219_CR13","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. J Algorithms 31:228\u2013248","journal-title":"J Algorithms"},{"key":"9219_CR14","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani V (2001) Approximation algorithms for facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J Assoc Cpmput Mach 48:274\u2013296","journal-title":"J Assoc Cpmput Mach"},{"key":"9219_CR15","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: Proceedings of the 34st annual ACM symposium on theory of computing (STOC\u201902), pp 731\u2013740","DOI":"10.1145\/509907.510012"},{"key":"9219_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 VV (2003) Greedy facility location algorithms analyzed using dual-fitting with factor-revealing LP. J Assoc Comput Mach 50:795\u2013824","journal-title":"J Assoc Comput Mach"},{"issue":"1","key":"9219_CR17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"MY Kao","year":"1996","unstructured":"Kao MY, Reif JH, Tate SR (1996) Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf Comput 131(1):63\u201380","journal-title":"Inf Comput"},{"key":"9219_CR18","unstructured":"Lin JH, Vitter JS (1992) \u03b5-approximations with minimum packing constraint violation. In STOC\u201992, pp 771\u2013782"},{"key":"9219_CR19","volume-title":"Proc 17th symp on discrete algorithms (SODA)","author":"GL Lin","year":"2006","unstructured":"Lin GL, Nagarajan C, Rajamaran R, Williamson DP (2006) A general approach for incremental approximation and hierarchical clustering. In: Proc 17th symp on discrete algorithms (SODA). ACM\/SIAM, New York\/Philadelphia"},{"key":"9219_CR20","doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proc of the 5th international workshop on approximation algorithms for combinatorial optimization (APPROX\u201902), pp 229\u2013242","DOI":"10.1007\/3-540-45753-4_20"},{"issue":"3","key":"9219_CR21","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"RR Mettu","year":"2003","unstructured":"Mettu RR, Plaxton CG (2003) The online median problem. SIAM J Comput 32(3):816\u2013832","journal-title":"SIAM J Comput"},{"key":"9219_CR22","doi-asserted-by":"crossref","unstructured":"Meyerson A (2001) Online facility location. In: Proc of the 42nd IEEE symp on foundations of computer science (FOCS\u201901), pp 426\u2013431","DOI":"10.1109\/SFCS.2001.959917"},{"key":"9219_CR23","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems. In: Proc STOC\u201997, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"9219_CR24","doi-asserted-by":"crossref","unstructured":"Sviridenko M (2002) An 1.528-approximation algorithm for the metric uncapacitated facility location problem. In: Proc of the 9th conference on integer programming and combinatorial optimization","DOI":"10.1007\/3-540-47867-1_18"},{"key":"9219_CR25","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 (2007) A new approximation algorithm for the k-facility location problem. Theor Comput Sci 384:126\u2013135","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9219-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9219-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9219-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9219-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,3]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9219"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9219-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,3]]}}}