{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T23:43:13Z","timestamp":1723160593165},"reference-count":26,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2022,3,1]]},"DOI":"10.1587\/transinf.2021fcp0013","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T22:26:19Z","timestamp":1646087179000},"page":"503-507","source":"Crossref","is-referenced-by-count":1,"title":["An &lt;i&gt;O&lt;\/i&gt;(&lt;i&gt;n&lt;\/i&gt;&lt;sup&gt;2&lt;\/sup&gt;)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position"],"prefix":"10.1587","volume":"E105.D","author":[{"given":"Yasuaki","family":"KOBAYASHI","sequence":"first","affiliation":[{"name":"Kyoto University"}]},{"given":"Shin-ichi","family":"NAKANO","sequence":"additional","affiliation":[{"name":"Gunma University"}]},{"given":"Kei","family":"UCHIZAWA","sequence":"additional","affiliation":[{"name":"Yamagata University"}]},{"given":"Takeaki","family":"UNO","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}]},{"given":"Yutaro","family":"YAMAGUCHI","sequence":"additional","affiliation":[{"name":"Osaka University"}]},{"given":"Katsuhisa","family":"YAMANAKA","sequence":"additional","affiliation":[{"name":"Iwate University"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] P.K. 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 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, Dispersion on the line, IPSJ SIG Technical Reports, 2016-AL-158-3, 2016."},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] K. Amano and S. Nakano, \u201cAn approximation algorithm for the 2-dispersion problem,\u201d IEICE Trans. Inf. &amp; Syst., vol.E103-D, no.3, pp.506-508, 2020. 10.1587\/transinf.2019fcp0005","DOI":"10.1587\/transinf.2019FCP0005"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] T. Araki and S. Nakano, \u201cThe max-min dispersion on a line,\u201d Proc. COCOA 2018, LNCS 11346, pp.672-678, 2018. 10.1007\/978-3-030-04651-4_45","DOI":"10.1007\/978-3-030-04651-4_45"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] C. Baur and S.P. Fekete, \u201cApproximation of geometric dispersion problems,\u201d Proc. APPROX 1998, vol.1444, pp.63-75, 1998. 10.1007\/bfb0053964","DOI":"10.1007\/BFb0053964"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] B. Birnbaum and K.J. Goldman, \u201cAn improved analysis for a greedy remote-clique algorithm using factor-revealing LPs,\u201d Algorithmica, vol.55, no.1, pp.42-59, 2009. 10.1007\/s00453-007-9142-2","DOI":"10.1007\/s00453-007-9142-2"},{"key":"8","unstructured":"[8] A. Cevallos, F. Eisenbrand, and R. Zenklusen, \u201cMax-sum diversity via convex programming,\u201d Proc. SoCG 2016, pp.26:1-26:14, 2016."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] 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":"10","doi-asserted-by":"publisher","unstructured":"[10] B. Chandra and M.M. Halld\u00f3rsson, \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":"11","doi-asserted-by":"crossref","unstructured":"[11] Z. Drezner, Facility location: A Survey of Applications and Methods, Springer, 1995.","DOI":"10.1007\/978-1-4612-5355-6"},{"key":"12","unstructured":"[12] Z. Drezner and H.W. Hamacher, Facility Location: Applications and Theory, Springer, 2004."},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] E. Erkut, \u201cThe discrete <i>p<\/i>-dispersion problem,\u201d European Journal of Operational Research, vol.46, no.1, pp.48-60, 1990. 10.1016\/0377-2217(90)90297-o","DOI":"10.1016\/0377-2217(90)90297-O"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] E. Erkut, Y. \u00dclk\u00fcsal, and O. Yeni\u00e7erio\u011flu, \u201cA comparison of <i>p<\/i>-dispersion heuristics,\u201d Computers &amp; Operational Research, vol.21, no.10, pp.1103-1113, 1994. 10.1016\/0305-0548(94)90041-8","DOI":"10.1016\/0305-0548(94)90041-8"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] S.P. Fekete and H. Meijer, \u201cMaximum dispersion and geometric maximum weight cliques,\u201d Algorithmica, vol.38, no.3, pp.501-511, 2004. 10.1007\/s00453-003-1074-x","DOI":"10.1007\/s00453-003-1074-x"},{"key":"16","unstructured":"[16] G. Frederickson, \u201cOptimal algorithms for tree partitioning,\u201d Proc. SODA 1991, pp.168-177, 1991."},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] F.L. Gall, \u201cPowers of tensors and fast matrix multiplication,\u201d Proc. ISSAC 2014, pp.296-303, 2014. 10.1145\/2608628.2608664","DOI":"10.1145\/2608628.2608664"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] R. Hassin, S. Rubinstein, and A. Tamir, \u201cApproximation algorithms for maximum dispersion,\u201d Operation Research Letters, vol.21, no.3, pp.133-137, 1997. 10.1016\/s0167-6377(97)00034-5","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] 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 11653, pp.291-300, 2019. 10.1007\/978-3-030-26176-4_24","DOI":"10.1007\/978-3-030-26176-4_24"},{"key":"20","unstructured":"[20] Y. Kobayashi, S. Nakano, K. Uchizawa, T. Uno, Y. Yamaguchi, and K. Yamanaka, \u201cMax-min 3-dispersionon a convex polygon,\u201d Proc. EuroCG 2021, accepted, 2021."},{"key":"21","doi-asserted-by":"publisher","unstructured":"[22] S.S. Ravi, D.J. Rosenkrantz, and G.K. Tayi, \u201cHeuristic and special case algorithms for dispersion problems,\u201d Operations Research, vol.42, no.2, pp.299-310, 1994. 10.1287\/opre.42.2.299","DOI":"10.1287\/opre.42.2.299"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[23] 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":"23","unstructured":"[24] R.L. Rivest T.H. Cormen, C.E. Leiserson, and C. Stein, Introduction to algorithms, Third Edition, MIT Press, 2000."},{"key":"24","doi-asserted-by":"crossref","unstructured":"[25] K.-H. Tsai and D.-W. Wang, \u201cOptimal algorithms for circle partitioning,\u201d Proc. COCOON 1997, LNCS 1276, pp.304-310, 1997. 10.1007\/bfb0045097","DOI":"10.1007\/BFb0045097"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[26] D.W. Wang and Y.-S. Kuo, \u201cA study on two geometric location problems,\u201d Information Processing Letters, vol.28, no.6, pp.281-286, 1988. 10.1016\/0020-0190(88)90174-3","DOI":"10.1016\/0020-0190(88)90174-3"},{"key":"26","doi-asserted-by":"crossref","unstructured":"[27] H. Yuan and M.J. Atallah, \u201cData structures for range minimum queries in multidimensional arrays,\u201d Proc. SODA 2010, pp.150-160, 2010. 10.1137\/1.9781611973075.14","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/3\/E105.D_2021FCP0013\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T04:04:58Z","timestamp":1646453098000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/3\/E105.D_2021FCP0013\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2021fcp0013","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,1]]},"article-number":"2021FCP0013"}}