Name
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 is an element of P, we want to find a subset S. P with vertical bar S vertical bar = k such that cost(S) = min{d(p, q) vertical bar p, q is an element of 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-78455-7_20 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Dispersion problem,Algorithm | Conference | 10823 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 10 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshihiro Akagi | 1 | 0 | 0.34 |
| Tetsuya Araki | 2 | 0 | 0.34 |
| Takashi Horiyama | 3 | 81 | 19.76 |
| Shin-ichi Nakano | 4 | 246 | 24.40 |
| Yoshio Okamoto | 5 | 170 | 28.50 |
| Yota Otachi | 6 | 161 | 37.16 |
| Toshiki Saitoh | 7 | 87 | 14.95 |
| Ryuhei Uehara | 8 | 528 | 75.38 |
| Takeaki Uno | 9 | 1319 | 107.99 |
| Kunihiro Wasa | 10 | 13 | 10.85 |