TY - GEN
T1 - Efficient approximations for the online dispersion problem
AU - Chen, Jing
AU - Li, Bo
AU - Li, Yingkai
N1 - Publisher Copyright:
© Jing Chen, Bo Li, and Yingkai Li;.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a κ-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2 ln 2+ϵ)-competitive, where ϵ > 0 can be arbitrarily small and the algorithm's running time is polynomial in 1/ϵ. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary κ-dimensional polytopes with κ ≥ 2, we provide a 2/1-ϵ-competitive algorithm and a 7/6 lower-bound. All our lower-bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary κ-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.
AB - The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a κ-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2 ln 2+ϵ)-competitive, where ϵ > 0 can be arbitrarily small and the algorithm's running time is polynomial in 1/ϵ. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary κ-dimensional polytopes with κ ≥ 2, we provide a 2/1-ϵ-competitive algorithm and a 7/6 lower-bound. All our lower-bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary κ-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.
KW - Competitive algorithms
KW - Dispersion
KW - Geometric optimization
KW - Online algorithms
KW - Packing
UR - http://www.scopus.com/inward/record.url?scp=85027272232&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2017.11
DO - 10.4230/LIPIcs.ICALP.2017.11
M3 - Conference article published in proceeding or book
AN - SCOPUS:85027272232
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
A2 - Muscholl, Anca
A2 - Indyk, Piotr
A2 - Kuhn, Fabian
A2 - Chatzigiannakis, Ioannis
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Y2 - 10 July 2017 through 14 July 2017
ER -