{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T08:40:09Z","timestamp":1748508009314,"version":"3.41.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T00:00:00Z","timestamp":1437091200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (CN)","doi-asserted-by":"publisher","award":["No.71071123"],"award-info":[{"award-number":["No.71071123"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (CN)","doi-asserted-by":"publisher","award":["No.60921003"],"award-info":[{"award-number":["No.60921003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the PCSIRT of the Ministry of Education of China","award":["No.1173"],"award-info":[{"award-number":["No.1173"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s10878-015-9933-3","type":"journal-article","created":{"date-parts":[[2015,7,16]],"date-time":"2015-07-16T03:42:32Z","timestamp":1437018152000},"page":"1219-1227","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An incremental version of the k-center problem on boundary of a convex polygon"],"prefix":"10.1007","volume":"30","author":[{"given":"Hai","family":"Du","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,17]]},"reference":[{"key":"9933_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:412\u2013458","journal-title":"ACM Comput Surv"},{"key":"9933_CR2","doi-asserted-by":"crossref","unstructured":"Bose P, Toussaint G (1996) Computing the constrained Euclidean, geodesic and link center of a simple polygon with applications, Proceedings of pacific graphics, International pp 102\u2013112","DOI":"10.1109\/CGI.1996.511792"},{"key":"9933_CR3","doi-asserted-by":"crossref","unstructured":"Charikar M, Chekuri C, Feder T, Motwani R (1997) Incremental clustering and dynamic information retrieval, In: Proceedings 29th ACM Symposium on theory of computing (STOC97) pp 626\u2013635","DOI":"10.1145\/258533.258657"},{"issue":"2","key":"9933_CR4","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M Charikar","year":"2004","unstructured":"Charikar M, Panigrahy R (2004) Clustering to minimize the sum of cluster diameters. J Comput Syst Sci 68(2):417\u2013441","journal-title":"J Comput Syst Sci"},{"key":"9933_CR5","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/j.tcs.2009.07.006","volume":"412","author":"M Chrobak","year":"2011","unstructured":"Chrobak M, Hurand M (2011) Better bounds for incremental medians. Theor Comput Sci 412:594\u2013601","journal-title":"Theor Comput Sci"},{"key":"9933_CR6","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/s00453-007-9005-x","volume":"50","author":"M Chrobak","year":"2008","unstructured":"Chrobak M, Kenyon C, Noga J, Young NE (2008) Incremental medians via online bidding. Algorithmica 50:455\u2013478","journal-title":"Algorithmica"},{"issue":"2","key":"9933_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s00453-011-9586-2","volume":"65","author":"J Csirik","year":"2013","unstructured":"Csirik J, Epstein L, Imreh LC, Levin A (2013) Online clustering with variable sized clusters. Algorithmica 65(2):251\u2013274","journal-title":"Algorithmica"},{"issue":"2","key":"9933_CR8","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1142\/S0129054108005747","volume":"19","author":"GK Das","year":"2008","unstructured":"Das GK, Roy S, Das S, Nandy SC (2008) Variations of base station placement problem on the boundary of a convex region. Int J Found Comput Sci 19(2):405\u2013427","journal-title":"Int J Found Comput Sci"},{"key":"9933_CR9","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 (2005) Performance guarantees for hierarchical clustering. J Comput Syst Sci 70:555\u2013569","journal-title":"J Comput Syst Sci"},{"key":"9933_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2013.07.008","volume":"500","author":"MR Ehmsen","year":"2013","unstructured":"Ehmsen MR, Larsen KS (2013) Better bounds on online unit clustering. Theor Comput Sci 500:1\u201324","journal-title":"Theor Comput Sci"},{"key":"9933_CR11","doi-asserted-by":"crossref","unstructured":"Feder T and Greene D H (1988) Optimal algorithms for approximate clustering, In: Proceedings of the 20th annual ACM symposium on theory of computing pp 434-444","DOI":"10.1145\/62212.62255"},{"issue":"1","key":"9933_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9049-y","volume":"50","author":"D Fotakis","year":"2008","unstructured":"Fotakis D (2008) On the competitive ratio for online facility location. Algorithmica 50(1):1\u201357","journal-title":"Algorithmica"},{"issue":"26","key":"9933_CR13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2013.03.010","volume":"540","author":"D Fotakis","year":"2014","unstructured":"Fotakis D, Koutris P (2014) Online sum-radii clustering. Theor Comput Sci 540(26):27\u201339","journal-title":"Theor Comput Sci"},{"key":"9933_CR14","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonz\u00e1lez","year":"1985","unstructured":"Gonz\u00e1lez TF (1985) Clustering to minimize the maximum intercluster distance. Theor Comput Sci 38:293\u2013306","journal-title":"Theor Comput Sci"},{"key":"9933_CR15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1006\/jagm.2001.1194","volume":"42","author":"D Halperin","year":"2002","unstructured":"Halperin D, Sharir M, Goldberg K (2002) The 2-center problem with obstacles. J Algorithms 42:109\u2013134","journal-title":"J Algorithms"},{"key":"9933_CR16","unstructured":"Hurtado F, Sacriscan V, Toussaint G (2000) Facility location problems with constraints. Stud Locat Anal 15:17\u201335"},{"key":"9933_CR17","unstructured":"Hartline J, Sharp A (2006) An incremental model for combinatorial minimization, technical report. Available at http:\/\/ecommons.cornell.edu\/bitstream\/1813\/5732\/1\/TR2006-2034.pdf . Accessed 5 July 2006"},{"key":"9933_CR18","first-page":"521","volume-title":"Approximation algorithms for NP-hard problems","author":"S Irani","year":"1996","unstructured":"Irani S, Karlin A (1996) Online computation. In: Hochbaum DS (ed) Approximation algorithms for NP-hard problems. PWS, Boston, MA, pp 521\u2013564"},{"key":"9933_CR19","doi-asserted-by":"crossref","unstructured":"Lin G, Nagarajan C, Rajaraman R and Williamson D P (2006) A general approach for incremental approximation and hierarchical clustering, In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms. ACM\/SIAM, New York","DOI":"10.1145\/1109557.1109684"},{"key":"9933_CR20","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:816\u2013832","journal-title":"SIAM J Comput"},{"key":"9933_CR21","doi-asserted-by":"crossref","unstructured":"Meyerson A (2001) Online facility location, In: Proceedings of the 42nd IEEE symposium on foundations of computer science (FOCS 01) pp 426\u2013431","DOI":"10.1109\/SFCS.2001.959917"},{"key":"9933_CR22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.jpdc.2007.08.005","volume":"68","author":"S Roy","year":"2008","unstructured":"Roy S, Bardhan D, Das S (2008) Base station placement on boundary of a convex polygon. J Parallel Distrib Comput 68:265\u2013273","journal-title":"J Parallel Distrib Comput"},{"key":"9933_CR23","doi-asserted-by":"crossref","unstructured":"Plaxton C G (2003) Approximation algorithms for hierarchical location problems, In: Proceedings of the 35th annual ACM symposium on theory of Computing. ACM Press, New York pp 40\u201349","DOI":"10.1145\/780542.780549"},{"key":"9933_CR24","unstructured":"Sharp A (2007) Incremental algorithms: solving problems in a changing world, Ph.D. Thesis, Cornell University"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9933-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9933-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9933-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T08:02:36Z","timestamp":1748505756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9933-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,17]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9933"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9933-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2015,7,17]]}}}