{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:18:22Z","timestamp":1742955502959,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031491894"},{"type":"electronic","value":"9783031491900"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49190-0_15","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"209-219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Variants of\u00a0Euclidean k-Center Clusterings"],"prefix":"10.1007","author":[{"given":"Shin-ichi","family":"Nakano","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P Agarwal","year":"1998","unstructured":"Agarwal, P., Sharir, M.: Efficient algorithms for geometric optimization. ACM Comput. Surv. 30, 412\u2013458 (1998)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"15_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1798596.1798602","volume":"6","author":"G Aggarwal","year":"2010","unstructured":"Aggarwal, G., et al.: Achieving anonymity via clustering. Trans. Algorithms 6(3), 1\u201319 (2010)","journal-title":"Trans. Algorithms"},{"key":"15_CR3","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications. Prentice Hall, Upper Saddle River (1993)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Aziz, H., Chan, H., Lee, B., Li, B., Walsh, T.: Facility location problem with capacity constraints: algorithmic and mechanism design perspectives. In Proceedings of AAAI 2020, pp. 1806\u20131813. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i02.5547"},{"issue":"3","key":"15_CR5","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jagm.1993.1047","volume":"15","author":"J Bar-Ilan","year":"1993","unstructured":"Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15(3), 385\u2013415 (1993)","journal-title":"J. Algorithms"},{"key":"15_CR6","unstructured":"Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. Approximation algorithms for NP-hard problems, pp. 296\u2013345 (1996)"},{"issue":"2","key":"15_CR7","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1142\/S0218195911003597","volume":"21","author":"P Brass","year":"2011","unstructured":"Brass, P., Knauer, C., Na, H., Shin, C., Vigneron, A.: The aligned k-center problem. Int. J. Comput. Geom. Appl. 21(2), 157\u2013178 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2015.05.028","volume":"592","author":"D Chen","year":"2015","unstructured":"Chen, D., Li, J., Wang, H.: Efficient algorithms for the one-dimensional k-center problem. Theor. Comput. Sci. 592, 135\u2013142 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR9","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd Edition. MIT Press, Cambridge (2009)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M.T., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: Proceedings of FOCS 2012, pp. 273\u2013282. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-319-62127-2_28","volume-title":"Algorithms and Data Structures","author":"H Ding","year":"2017","unstructured":"Ding, H., Hu, L., Huang, L., Li, J.: Capacitated center problems with two-sided bounds and outliers. In: WADS 2017. LNCS, vol. 10389, pp. 325\u2013336. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-62127-2_28"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Feder , T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of STOC 1988, pp. 434\u2013444. ACM (1988)","DOI":"10.1145\/62212.62255"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2014.01.026","volume":"527","author":"T Ghasemi","year":"2014","unstructured":"Ghasemi, T., Razzazi, M.: A PTAS for the cardinality constrained covering with unit balls. Theor. Comput. Sci. 527, 50\u201360 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR15","doi-asserted-by":"publisher","unstructured":"Hwang, R.Z., Richard C. T. Lee, and R. C. Chang. The slab dividing approach to solve the Euclidean p-center problem. Algorithmica 9(1), 1\u201322 (1993). https:\/\/doi.org\/10.1007\/BF01185335","DOI":"10.1007\/BF01185335"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/s10878-012-9452-4","volume":"25","author":"A Karmakar","year":"2013","unstructured":"Karmakar, A., Das, S., Nandy, S.C., Bhattacharya, B.K.: Some variations on constrained minimum enclosing circle problem. J. Comb. Optim. 25, 176\u2013190 (2013)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"15_CR17","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480197329776","volume":"13","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Sussmann, Y.J.: The capacitated K-center problem. SIAM J. Discret. Math. 13(3), 403\u2013418 (2000)","journal-title":"SIAM J. Discret. Math."},{"key":"15_CR18","unstructured":"Kumar, A.: Capacitated k-center problem with vertex weights. In: Proceedings of FSTTCS 2016, vol. 65 of LIPIcs, pp. 8:1\u20138:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM J. Comput. 13, 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"15_CR20","doi-asserted-by":"publisher","first-page":"837","DOI":"10.7155\/jgaa.00514","volume":"23","author":"S Nakano","year":"2019","unstructured":"Nakano, S.: A simple algorithm for r-gatherings on the line. J. Graph Algorithms Appl. 23(5), 837\u2013845 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1142\/S0218195916600049","volume":"26","author":"H Wang","year":"2016","unstructured":"Wang, H., Zhang, J.: Line-constrained k-median, k-means, and k-center problems in the plane. Int. J. Comput. Geom. Appl. 26, 185\u2013210 (2016)","journal-title":"Int. J. Comput. Geom. Appl."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49190-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:09:41Z","timestamp":1702026581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49190-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491894","9783031491900"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49190-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}