Exact Algorithms for the Max-Min Dispersion Problem. Akagi, T., Araki, T., Horiyama, T., Nakano, S., Okamoto, Y., Otachi, Y., Saitoh, T., Uehara, R., Uno, T., & Wasa, K. In Chen, J. & Lu, P., editors, Proceedings of the 12th International Workshop on Frontiers in Algorithmics (FAW 2018), Guangzhou, China, May 8–10, 2018, volume 10823, of Lecture Notes in Computer Science, pages 263–272, Cham, 2018. Springer International Publishing. . Acceptance ratio = 23/38.![Exact Algorithms for the Max-Min Dispersion Problem [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex Given a set $P$ of $n$ elements, and a function $d$ that assigns a non-negative real number $d(p, q)$ for each pair of elements $p,q ∈P$, we want to find a subset $S⊆P$ with $|S|=k$ such that $\mathop {\mathrm{cost}}(S)= \min \{ d(p,q) ∣p,q ∈S\}$ is maximized. This is the max-min $k$-dispersion problem. In this paper, exact algorithms for the max-min $k$-dispersion problem are studied. We first show the max-min $k$-dispersion problem can be solved in $O(n^{ωk/3} \log n)$time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain $O(n)$-time algorithms after sorting.
@InProceedings{Akagi:Araki:Horiyama:Nakano:Okamoto:Otachi:Saito:Uehara:Uno:Wasa:FAW2018,
author = "Akagi, Toshihiro and Araki, Tetsuya and Horiyama, Takashi and Nakano, Shin-ichi and Okamoto, Yoshio and Otachi, Yota and Saitoh, Toshiki and Uehara, Ryuhei and Uno, Takeaki and Wasa, Kunihiro",
editor = "Chen, Jianer and Lu, Pinyan",
title = "Exact Algorithms for the Max-Min Dispersion Problem",
booktitle = "Proceedings of the 12th International Workshop on Frontiers in Algorithmics (FAW 2018), Guangzhou, China, May 8–10, 2018",
year = "2018",
publisher = "Springer International Publishing. ",
address = "Cham",
pages = "263--272",
series = "Lecture Notes in Computer Science",
volume = 10823,
abstract = "Given a set $P$ of $n$ elements, and a function $d$ that assigns a non-negative real number $d(p, q)$ for each pair of elements $p,q \in P$, we want to find a subset $S\subseteq P$ with $|S|=k$ such that $\mathop {\mathrm{cost}}(S)= \min \{ d(p,q) \mid p,q \in S\}$ is maximized. This is the max-min $k$-dispersion problem. In this paper, exact algorithms for the max-min $k$-dispersion problem are studied. We first show the max-min $k$-dispersion problem can be solved in $O(n^{\omega k/3} \log n)$time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain $O(n)$-time algorithms after sorting.",
url = "https://doi.org/10.1007/978-3-319-78455-7_20",
doi = "10.1007/978-3-319-78455-7_20",
note = "Acceptance ratio = 23/38.",
}
Downloads: 0
{"_id":"9uAnkhmeCgKLN7hok","bibbaseid":"akagi-araki-horiyama-nakano-okamoto-otachi-saitoh-uehara-etal-exactalgorithmsforthemaxmindispersionproblem-2018","authorIDs":["552f686310c2c096480000c9"],"author_short":["Akagi, T.","Araki, T.","Horiyama, T.","Nakano, S.","Okamoto, Y.","Otachi, Y.","Saitoh, T.","Uehara, R.","Uno, T.","Wasa, K."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Akagi"],"firstnames":["Toshihiro"],"suffixes":[]},{"propositions":[],"lastnames":["Araki"],"firstnames":["Tetsuya"],"suffixes":[]},{"propositions":[],"lastnames":["Horiyama"],"firstnames":["Takashi"],"suffixes":[]},{"propositions":[],"lastnames":["Nakano"],"firstnames":["Shin-ichi"],"suffixes":[]},{"propositions":[],"lastnames":["Okamoto"],"firstnames":["Yoshio"],"suffixes":[]},{"propositions":[],"lastnames":["Otachi"],"firstnames":["Yota"],"suffixes":[]},{"propositions":[],"lastnames":["Saitoh"],"firstnames":["Toshiki"],"suffixes":[]},{"propositions":[],"lastnames":["Uehara"],"firstnames":["Ryuhei"],"suffixes":[]},{"propositions":[],"lastnames":["Uno"],"firstnames":["Takeaki"],"suffixes":[]},{"propositions":[],"lastnames":["Wasa"],"firstnames":["Kunihiro"],"suffixes":[]}],"editor":[{"propositions":[],"lastnames":["Chen"],"firstnames":["Jianer"],"suffixes":[]},{"propositions":[],"lastnames":["Lu"],"firstnames":["Pinyan"],"suffixes":[]}],"title":"Exact Algorithms for the Max-Min Dispersion Problem","booktitle":"Proceedings of the 12th International Workshop on Frontiers in Algorithmics (FAW 2018), Guangzhou, China, May 8–10, 2018","year":"2018","publisher":"Springer International Publishing. ","address":"Cham","pages":"263–272","series":"Lecture Notes in Computer Science","volume":"10823","abstract":"Given a set $P$ of $n$ elements, and a function $d$ that assigns a non-negative real number $d(p, q)$ for each pair of elements $p,q ∈P$, we want to find a subset $S⊆P$ with $|S|=k$ such that $\\mathop {\\mathrm{cost}}(S)= \\min \\{ d(p,q) ∣p,q ∈S\\}$ is maximized. This is the max-min $k$-dispersion problem. In this paper, exact algorithms for the max-min $k$-dispersion problem are studied. We first show the max-min $k$-dispersion problem can be solved in $O(n^{ωk/3} \\log n)$time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain $O(n)$-time algorithms after sorting.","url":"https://doi.org/10.1007/978-3-319-78455-7_20","doi":"10.1007/978-3-319-78455-7_20","note":"Acceptance ratio = 23/38.","bibtex":"@InProceedings{Akagi:Araki:Horiyama:Nakano:Okamoto:Otachi:Saito:Uehara:Uno:Wasa:FAW2018,\n author = \"Akagi, Toshihiro and Araki, Tetsuya and Horiyama, Takashi and Nakano, Shin-ichi and Okamoto, Yoshio and Otachi, Yota and Saitoh, Toshiki and Uehara, Ryuhei and Uno, Takeaki and Wasa, Kunihiro\",\n editor = \"Chen, Jianer and Lu, Pinyan\",\n title = \"Exact Algorithms for the Max-Min Dispersion Problem\",\n booktitle = \"Proceedings of the 12th International Workshop on Frontiers in Algorithmics (FAW 2018), Guangzhou, China, May 8–10, 2018\",\n year = \"2018\",\n publisher = \"Springer International Publishing. \",\n address = \"Cham\",\n pages = \"263--272\",\n series = \"Lecture Notes in Computer Science\", \n volume = 10823,\n abstract = \"Given a set $P$ of $n$ elements, and a function $d$ that assigns a non-negative real number $d(p, q)$ for each pair of elements $p,q \\in P$, we want to find a subset $S\\subseteq P$ with $|S|=k$ such that $\\mathop {\\mathrm{cost}}(S)= \\min \\{ d(p,q) \\mid p,q \\in S\\}$ is maximized. This is the max-min $k$-dispersion problem. In this paper, exact algorithms for the max-min $k$-dispersion problem are studied. We first show the max-min $k$-dispersion problem can be solved in $O(n^{\\omega k/3} \\log n)$time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain $O(n)$-time algorithms after sorting.\",\n url = \"https://doi.org/10.1007/978-3-319-78455-7_20\", \n doi = \"10.1007/978-3-319-78455-7_20\", \n note = \"Acceptance ratio = 23/38.\",\n}\n\n","author_short":["Akagi, T.","Araki, T.","Horiyama, T.","Nakano, S.","Okamoto, Y.","Otachi, Y.","Saitoh, T.","Uehara, R.","Uno, T.","Wasa, K."],"editor_short":["Chen, J.","Lu, P."],"key":"Akagi:Araki:Horiyama:Nakano:Okamoto:Otachi:Saito:Uehara:Uno:Wasa:FAW2018","id":"Akagi:Araki:Horiyama:Nakano:Okamoto:Otachi:Saito:Uehara:Uno:Wasa:FAW2018","bibbaseid":"akagi-araki-horiyama-nakano-okamoto-otachi-saitoh-uehara-etal-exactalgorithmsforthemaxmindispersionproblem-2018","role":"author","urls":{"Paper":"https://doi.org/10.1007/978-3-319-78455-7_20"},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/KunihiroWASA/publications_bib/master/publications.bib","creationDate":"2019-08-01T03:02:18.883Z","downloads":0,"keywords":[],"search_terms":["exact","algorithms","max","min","dispersion","problem","akagi","araki","horiyama","nakano","okamoto","otachi","saitoh","uehara","uno","wasa"],"title":"Exact Algorithms for the Max-Min Dispersion Problem","year":2018,"dataSources":["G5knAh5sDHZjd7TY8"]}