{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T01:01:04Z","timestamp":1740099664354,"version":"3.37.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030419127"},{"type":"electronic","value":"9783030419134"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41913-4_15","type":"book-chapter","created":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T19:04:50Z","timestamp":1581707090000},"page":"179-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Clustering a 2d Pareto Front: P-center Problems Are Solvable in Polynomial Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3775-5629","authenticated-orcid":false,"given":"Nicolas","family":"Dupin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5728-0726","authenticated-orcid":false,"given":"Frank","family":"Nielsen","sequence":"additional","affiliation":[]},{"given":"El-Ghazali","family":"Talbi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,15]]},"reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/PL00009387","volume":"20","author":"P Agarwal","year":"1998","unstructured":"Agarwal, P., Sharir, M., Welzl, E.: The discrete 2-center problem. Discret. Comput. Geom. 20(3), 287\u2013305 (1998)","journal-title":"Discret. Comput. Geom."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences. In: Proceedings of GECCO 2009, pp. 563\u2013570. ACM (2009)","DOI":"10.1145\/1569901.1569980"},{"key":"15_CR3","unstructured":"Brass, P., Knauer, C., Na, H., Shin, C., Vigneron, A.: Computing k-centers on a line. arXiv preprint \narXiv:0902.3282\n\n (2009)"},{"key":"15_CR4","unstructured":"Bringmann, K., Cabello, S., Emmerich, M.: Maximum volume subset selection for anchored boxes. arXiv preprint \narXiv:1803.00849\n\n (2018)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Friedrich, T., Klitzke, P.: Two-dimensional subset selection for hypervolume and epsilon-indicator. In: Annual Conference on Genetic and Evolutionary Computation, pp. 589\u2013596. ACM (2014)","DOI":"10.1145\/2576768.2598276"},{"issue":"12","key":"15_CR6","doi-asserted-by":"publisher","first-page":"2991","DOI":"10.1016\/j.cor.2013.07.011","volume":"40","author":"H Calik","year":"2013","unstructured":"Calik, H., Tansel, B.: Double bound method for solving the p-center location problem. Comput. Oper. Res. 40(12), 2991\u20132999 (2013)","journal-title":"Comput. Oper. Res."},{"issue":"8","key":"15_CR7","first-page":"741","volume":"35","author":"Z Drezner","year":"1984","unstructured":"Drezner, Z.: The p-centre problem - heuristic and optimal algorithms. J. Oper. Res. Soc. 35(8), 741\u2013748 (1984)","journal-title":"J. Oper. Res. Soc."},{"key":"15_CR8","unstructured":"Dupin, N., Nielsen, F., Talbi, E.: Dynamic programming heuristic for k-means clustering among a 2-dimensional pareto frontier. In: 7th International Conference on Metaheuristics and Nature Inspired Computing, pp. 1\u20138 (2018)"},{"key":"15_CR9","series-title":"Advances in Intelligent Systems and Computing","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/978-3-030-21803-4_79","volume-title":"Optimization of Complex Systems: Theory, Models, Algorithms and Applications","author":"N Dupin","year":"2020","unstructured":"Dupin, N., Nielsen, F., Talbi, E.-G.: K-medoids clustering is solvable in polynomial time for a 2d pareto front. In: Le Thi, H.A., Le, H.M., Pham Dinh, T. (eds.) WCGO 2019. AISC, vol. 991, pp. 790\u2013799. Springer, Cham (2020). \nhttps:\/\/doi.org\/10.1007\/978-3-030-21803-4_79"},{"key":"15_CR10","unstructured":"Dupin, N., Talbi, E.: Clustering in a 2-dimensional pareto front: p-median and p-center are solvable in polynomial time. arXiv preprint \narXiv:1806.02098\n\n (2018)"},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1287\/ijoc.1030.0028","volume":"16","author":"S Elloumi","year":"2004","unstructured":"Elloumi, S., Labb\u00e9, M., Pochet, Y.: A new formulation and resolution method for the p-center problem. INFORMS J. Comput. 16(1), 84\u201394 (2004)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"15_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R Fowler","year":"1981","unstructured":"Fowler, R., Paterson, M., Tanimoto, S.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"15_CR13","unstructured":"Gr\u00f8nlund, A., et al.: Fast exact k-means, k-medians and Bregman divergence clustering in 1d. arXiv preprint \narXiv:1701.07204\n\n (2017)"},{"issue":"3","key":"15_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W Hsu","year":"1979","unstructured":"Hsu, W., Nemhauser, G.: Easy and hard bottleneck location problems. Discret. Appl. Math. 1(3), 209\u2013215 (1979)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"15_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01185335","volume":"9","author":"R Hwang","year":"1993","unstructured":"Hwang, R., Lee, R., Chang, R.: The slab dividing approach to solve the Euclidean P-center problem. Algorithmica 9(1), 1\u201322 (1993)","journal-title":"Algorithmica"},{"issue":"2","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., et al.: Some variations on constrained minimum enclosing circle problem. J. Comb. Optim. 25(2), 176\u2013190 (2013)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"15_CR17","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1162\/EVCO_a_00157","volume":"24","author":"T Kuhn","year":"2016","unstructured":"Kuhn, T., et al.: Hypervolume subset selection in two dimensions: formulations and algorithms. Evol. Comput. 24(3), 411\u2013425 (2016)","journal-title":"Evol. Comput."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theoret. Comput. Sci. 442, 13\u201321 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"15_CR19","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12(4), 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"15_CR20","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(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR21","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0212051","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N., Tamir, A.: New results on the complexity of p-centre problems. SIAM J. Comput. 12(4), 751\u2013758 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"15_CR22","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s101070050128","volume":"87","author":"S Say\u0131n","year":"2000","unstructured":"Say\u0131n, S.: Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming. Math. Prog. 87(3), 543\u2013560 (2000)","journal-title":"Math. Prog."},{"issue":"2","key":"15_CR23","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00009311","volume":"18","author":"M Sharir","year":"1997","unstructured":"Sharir, M.: A near-linear algorithm for the planar 2-center problem. Discret. Comput. Geom. 18(2), 125\u2013134 (1997)","journal-title":"Discret. Comput. Geom."},{"key":"15_CR24","doi-asserted-by":"publisher","DOI":"10.1002\/9780470496916","volume-title":"Metaheuristics: From Design to Implementation","author":"E Talbi","year":"2009","unstructured":"Talbi, E.: Metaheuristics: From Design to Implementation, vol. 74. Wiley, Hoboken (2009)"},{"issue":"2","key":"15_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.32614\/RJ-2011-015","volume":"3","author":"H Wang","year":"2011","unstructured":"Wang, H., Song, M.: Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. R J. 3(2), 29 (2011)","journal-title":"R J."},{"issue":"3","key":"15_CR26","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1016\/j.ejor.2010.10.021","volume":"210","author":"E Zio","year":"2011","unstructured":"Zio, E., Bazzo, R.: A clustering procedure for reducing the number of representative solutions in the pareto front of multiobjective optimization problems. Eur. J. Oper. Res. 210(3), 624\u2013634 (2011)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Communications in Computer and Information Science","Optimization and Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41913-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T19:11:38Z","timestamp":1581707498000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41913-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030419127","9783030419134"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41913-4_15","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"15 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"OLA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Optimization and Learning","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"C\u00e1diz","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 February 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ola2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ola2020.sciencesconf.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"sciencesconf.org","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"55","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":"23","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":"42% - 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":"4","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)"}}]}}