Dumitrescu, Adrian ;
Jiang, Minghui
Dispersion in Unit Disks
Abstract
We present two new approximation algorithms with (improved) constant ratios for selecting $n$ points in $n$ unit disks such that the minimum pairwise distance among the points is maximized.
(I) A very simple $O(n \log{n})$time algorithm with ratio $0.5110$ for disjoint unit disks. In combination with an algorithm of Cabello~\cite{Ca07}, it yields a $O(n^2)$time algorithm
with ratio of $0.4487$ for dispersion in $n$ not necessarily disjoint
unit disks.
(II) A more sophisticated LPbased algorithm with ratio $0.6495$ for
disjoint unit disks that uses a linear number of variables and
constraints, and runs in polynomial time.
The algorithm introduces a novel technique which combines linear
programming and projections for approximating distances.
The previous best approximation ratio for disjoint unit disks was $\frac{1}{2}$. Our results give a partial answer to an open question raised by Cabello~\cite{Ca07}, who asked whether $\frac{1}{2}$ could be improved.
BibTeX  Entry
@InProceedings{dumitrescu_et_al:LIPIcs:2010:2464,
author = {Adrian Dumitrescu and Minghui Jiang},
title = {{Dispersion in Unit Disks}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {299310},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2464},
URN = {urn:nbn:de:0030drops24646},
doi = {10.4230/LIPIcs.STACS.2010.2464},
annote = {Keywords: Dispersion problem, linear programming, approximation algorithm}
}
2010
Keywords: 

Dispersion problem, linear programming, approximation algorithm 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

2010 