Chen, Jing ;
Li, Bo ;
Li, Yingkai
Efficient Approximations for the Online Dispersion Problem
Abstract
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 kdimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many realworld 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 alltime worstcase (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 nontrivial even on a segment. For cumulative distance, this remains the case even when the problem is timedependent but offline, with all the arriving and departure times given in advance.
For the online ATWC problem on a segment, we construct a deterministic polynomialtime algorithm which is (2ln2+epsilon)competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591competitive algorithm and a 1.183 lowerbound. Furthermore, for arbitrary kdimensional polytopes with k>=2, we provide a 2/(1epsilon)competitive algorithm and a 7/6 lowerbound. All our lowerbounds 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 kdimensional polytopes, we provide a polynomialtime blackbox 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.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2017:7400,
author = {Jing Chen and Bo Li and Yingkai Li},
title = {{Efficient Approximations for the Online Dispersion Problem}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {11:111:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7400},
URN = {urn:nbn:de:0030drops74002},
doi = {10.4230/LIPIcs.ICALP.2017.11},
annote = {Keywords: dispersion, online algorithms, geometric optimization, packing, competitive algorithms}
}
2017
Keywords: 

dispersion, online algorithms, geometric optimization, packing, competitive algorithms 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 