{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T20:52:29Z","timestamp":1771275149949,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Kakenhi","doi-asserted-by":"crossref","award":["17K00003"],"award-info":[{"award-number":["17K00003"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00549-5","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T12:03:04Z","timestamp":1582632184000},"page":"1824-1830","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Max\u2013min dispersion on a line"],"prefix":"10.1007","volume":"44","author":[{"given":"Tetsuya","family":"Araki","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2368-6183","authenticated-orcid":false,"given":"Shin-ichi","family":"Nakano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"549_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 (1998) Efficient algorithms for geometric optimization. Comput Surv 30:412\u2013458","journal-title":"Comput Surv"},{"key":"549_CR2","unstructured":"Akagi T, Nakano S (2016) Dispersion on the line, IPSJ SIG Technical Reports, 2016-AL-158-3"},{"key":"549_CR3","doi-asserted-by":"crossref","unstructured":"Akagi T, Araki T, Horiyama T, Nakano S, Okamoto Y, Otachi Y, Saitoh T, Uehara R, Uno T, Wasa K (2018) Exact algorithms for the max\u2013min dispersion problem. In: Proceedings of FAW 2018, vol 10823. LNCS, pp 263\u2013272","DOI":"10.1007\/978-3-319-78455-7_20"},{"key":"549_CR4","doi-asserted-by":"crossref","unstructured":"Araki T, Nakano S (2018) The max\u2013min dispersion on a line. In: Proceedings of COCOA 2018, vol 11346. LNCS, pp 672\u2013678","DOI":"10.1007\/978-3-030-04651-4_45"},{"key":"549_CR5","doi-asserted-by":"crossref","unstructured":"Baur C, Fekete SP (1998) Approximation of geometric dispersion problems. In: Proceedings of APPROX 1998, pp 63\u201375","DOI":"10.1007\/BFb0053964"},{"key":"549_CR6","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/s00453-007-9142-2","volume":"50","author":"B Birnbaum","year":"2009","unstructured":"Birnbaum B, Goldman KJ (2009) An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 50:42\u201359","journal-title":"Algorithmica"},{"key":"549_CR7","unstructured":"Cevallos A, Eisenbrand F, Zenklusen R (2016) Max-sum diversity via convex programming. In: Proceedings of SoCG 2016, pp 26:1\u201326:14"},{"key":"549_CR8","doi-asserted-by":"crossref","unstructured":"Cevallos A, Eisenbrand F, Zenklusen R (2017) Local search for max-sum diversification. In: Proceedings of SODA 2017, pp 130\u2013142","DOI":"10.1137\/1.9781611974782.9"},{"key":"549_CR9","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1006\/jagm.2000.1145","volume":"38","author":"B Chandra","year":"2001","unstructured":"Chandra B, Halldorsson MM (2001) Approximation algorithms for dispersion problems. J Algorithms 38:438\u2013465","journal-title":"J Algorithms"},{"key":"549_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5355-6","volume-title":"Facility location: a survey of applications and methods","author":"Z Drezner","year":"1995","unstructured":"Drezner Z (1995) Facility location: a survey of applications and methods. Springer, Berlin"},{"key":"549_CR11","volume-title":"Facility location: applications and theory","author":"Z Drezner","year":"2004","unstructured":"Drezner Z, Hamacher HW (2004) Facility location: applications and theory. Springer, Berlin"},{"key":"549_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0377-2217(90)90297-O","volume":"46","author":"E Erkut","year":"1990","unstructured":"Erkut E (1990) The discrete $$p$$-dispersion problem. Eur J Oper Res 46:48\u201360","journal-title":"Eur J Oper Res"},{"key":"549_CR13","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00453-003-1074-x","volume":"38","author":"SP Fekete","year":"2004","unstructured":"Fekete SP, Meijer H (2004) Maximum dispersion and geometric maximum weight cliques. Algorithmica 38:501\u2013511","journal-title":"Algorithmica"},{"key":"549_CR14","unstructured":"Frederickson G (1991) Optimal algorithms for tree partitioning. In: Proceedings of SODA 1991, pp 168\u2013177"},{"key":"549_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0167-6377(97)00034-5","volume":"21","author":"R Hassin","year":"1997","unstructured":"Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper Res Lett 21:133\u2013137","journal-title":"Oper Res Lett"},{"key":"549_CR16","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper Res 42:299\u2013310","journal-title":"Oper Res"},{"key":"549_CR17","first-page":"241","volume":"42","author":"M Sydow","year":"2014","unstructured":"Sydow M (2014) Approximation guarantees for max sum and max min facility dispersion with parameterised triangle inequality and applications in result diversification. Math Appl 42:241\u2013257","journal-title":"Math Appl"},{"key":"549_CR18","doi-asserted-by":"crossref","unstructured":"Tsai KH, Wang DW (1997) Optimal algorithms for circle partitioning. In: Proceedings of COCOON 1997, vol 1276. LNCS, pp 304\u2013310","DOI":"10.1007\/BFb0045097"},{"key":"549_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"DW Wang","year":"1988","unstructured":"Wang DW, Kuo Y-S (1988) A study on two geometric location problems. Inf Process Lett 28:281\u2013286","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00549-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00549-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00549-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:45:57Z","timestamp":1664354757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00549-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,25]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["549"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00549-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,25]]},"assertion":[{"value":"25 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}