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.

Paper doi abstract bibtex

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