{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T20:54:07Z","timestamp":1771275247513,"version":"3.50.1"},"reference-count":21,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2021,9,1]]},"DOI":"10.1587\/transfun.2020dmp0003","type":"journal-article","created":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T22:07:12Z","timestamp":1616105232000},"page":"1101-1107","source":"Crossref","is-referenced-by-count":2,"title":["Max-Min 3-Dispersion Problems"],"prefix":"10.1587","volume":"E104.A","author":[{"given":"Takashi","family":"HORIYAMA","sequence":"first","affiliation":[{"name":"Hokkaido University"}]},{"given":"Shin-ichi","family":"NAKANO","sequence":"additional","affiliation":[{"name":"Gunma University"}]},{"given":"Toshiki","family":"SAITOH","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology"}]},{"given":"Koki","family":"SUETSUGU","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]},{"given":"Akira","family":"SUZUKI","sequence":"additional","affiliation":[{"name":"Tohoku University"}]},{"given":"Ryuhei","family":"UEHARA","sequence":"additional","affiliation":[{"name":"JAIST"}]},{"given":"Takeaki","family":"UNO","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]},{"given":"Kunihiro","family":"WASA","sequence":"additional","affiliation":[{"name":"Toyohashi University of Technology"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] P. Agarwal and M. Sharir, \u201cEfficient algorithms for geometric optimization,\u201d ACM Comput. Surv., vol.30, no.4, pp.412-458, 1998. 10.1145\/299917.299918","DOI":"10.1145\/299917.299918"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] T. Akagi, T. Araki, T. Horiyama, S. Nakano, Y. Okamoto, Y. Otachi, T. Saitoh, R. Uehara, T. Uno, and K. Wasa, \u201cExact algorithms for the max-min dispersion problem,\u201d Proc. FAW 2018, LNCS, vol.10823, pp.263-272, 2018. 10.1007\/978-3-319-78455-7_20","DOI":"10.1007\/978-3-319-78455-7_20"},{"key":"3","unstructured":"[3] T. Akagi and S. Nakano, \u201cDispersion on the line,\u201d IPSJ SIG Technical Reports, 2016-AL-158-3, 2016."},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] T. Araki and S. Nakano, \u201cThe max-min dispersion on a line,\u201d Proc. COCOA 2018, LNCS, vol.11346, pp.672-678, 2018. 10.1007\/978-3-030-04651-4_45","DOI":"10.1007\/978-3-030-04651-4_45"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] C. Baur and S.P. Fekete, \u201cApproximation of geometric dispersion problems,\u201d Proc. APPROX 1998, pp.63-75, 1998. 10.1007\/bfb0053964","DOI":"10.1007\/BFb0053964"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] B. Birnbaum and K.J. Goldman, \u201cAn improved analysis for a greedy remote-clique algorithm using factor-revealing LPs,\u201d Algorithmica, vol.50, pp.42-59, 2009. 10.1007\/s00453-007-9142-2","DOI":"10.1007\/s00453-007-9142-2"},{"key":"7","unstructured":"[7] A. Cevallos, F. Eisenbrand, and R. Zenklusen, \u201cMax-sum diversity via convex programming,\u201d Proc. SoCG 2016, pp.26:1-26:14, 2016."},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] A. Cevallos, F. Eisenbrand, and R. Zenklusen, \u201cLocal search for max-sum diversification,\u201d Proc. SODA 2017, pp.130-142, 2017. 10.1137\/1.9781611974782.9","DOI":"10.1137\/1.9781611974782.9"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] B. Chandra and M.M. Halldorsson, \u201cApproximation algorithms for dispersion problems,\u201d J. Algorithms, vol.38, no.2, pp.438-465, 2001. 10.1006\/jagm.2000.1145","DOI":"10.1006\/jagm.2000.1145"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, 1995.","DOI":"10.1007\/978-1-4612-5355-6"},{"key":"11","unstructured":"[11] Z. Drezner and H.W. Hamacher, Facility Location: Applications and Theory, Springer, 2004."},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] E. Erkut, \u201cThe discrete <i>p<\/i>-dispersion problem,\u201d Eur. J. Oper. Res., vol.46, no.1, pp.48-60, 1990. 10.1016\/0377-2217(90)90297-o","DOI":"10.1016\/0377-2217(90)90297-O"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] S.P. Fekete and H. Meijer, \u201cMaximum dispersion and geometric maximum weight cliques,\u201d Algorithmica, vol.38, pp.501-511, 2004. 10.1007\/s00453-003-1074-x","DOI":"10.1007\/s00453-003-1074-x"},{"key":"14","unstructured":"[14] G. Frederickson, \u201cOptimal algorithms for tree partitioning,\u201d Proc. SODA 1991, pp.168-177, 1991."},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] T. Horiyama, S. Nakano, T. Saitoh, K. Suetsugu, A. Suzuki, R. Uehara, T. Uno, and K. Wasa, \u201cMax-min 3-dispersion problems,\u201d Proc. COCOON 2019, LNCS, vol.11653, pp.291-300, 2019. 10.1007\/978-3-030-26176-4_24","DOI":"10.1007\/978-3-030-26176-4_24"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] S. Rubinstein R. Hassin, and A. Tamir, \u201cApproximation algorithms for maximum dispersion,\u201d Oper. Res. Lett., vol.21, no.3, pp.133-137, 1997. 10.1016\/s0167-6377(97)00034-5","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[18] E.A. Ramos, \u201cDeterministic algorithms for 3-D diameter and some 2-D lower envelopes,\u201d Proc. Symposium on Computational Geometry 2000, pp.290-299, 2000. 10.1145\/336154.336215","DOI":"10.1145\/336154.336215"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[19] S.S. Ravi, D.J. Rosenkrantz, and G.K. Tayi, \u201cHeuristic and special case algorithms for dispersion problems,\u201d Oper. Res., vol.42, no.2, pp.299-310, 1994. 10.1287\/opre.42.2.299","DOI":"10.1287\/opre.42.2.299"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[20] M. Sydow, \u201cApproximation guarantees for max sum and max min facility dispersion with parameterised triangle inequality and applications in result diversification,\u201d Mathematica Applicanda, vol.42, no.2, pp.241-257, 2014. 10.14708\/ma.v42i2.547","DOI":"10.14708\/ma.v42i2.547"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] D.W. Wang and Y.-S. Kuo, \u201cA study on two geometric location problems,\u201d Inform. Process. Lett., vol.28, no.6, pp.281-286, 1988. 10.1016\/0020-0190(88)90174-3","DOI":"10.1016\/0020-0190(88)90174-3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[22] A.C. Yao, \u201cOn constructing minimum spanning trees in <i>k<\/i>-dimensional spaces and related problems,\u201d SIAM J. Comput., vol.11, no.4, pp.721-736, 1982. 10.1137\/0211059","DOI":"10.1137\/0211059"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/9\/E104.A_2020DMP0003\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,4]],"date-time":"2021-09-04T03:23:48Z","timestamp":1630725828000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/9\/E104.A_2020DMP0003\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,1]]},"references-count":21,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2020dmp0003","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,1]]},"article-number":"2020DMP0003"}}