"Approximation of Geometric Dispersion Problems"
Article by Christoph Baur, Sandor P. Fekete, available as BibTeX Source, postscript file and compressed postscript file.
Mathematisches Institut, Universität zu Köln
Preprint Key:	zpr97-296
Keywords:	approximation algorithms, bounds for approximation factors, computational geometry, dispersion, geometric optimization, NP-completeness, packing
MSC codes:	68Q25, 68U05, 90C30
This article was published in July 1998 by Springer in the proceedings "Short version in: Approximation Algorithms for Combinatorial Optimization (APPROX 98)" (edited by K. Jansen, J. Rolim), series "Lecture Notes in Computer Science", volume 1444, number 296, pages 63--75.
Abstract:	We consider problems of distributing a number of points within a polygonal region P, such that the points are ''far away'' from each other. Problems of this type have been considered before for the case where the possible locations form a discrete set. Dispersion problems are closely related to packing problems. While Hochbaum and Maass (1985) have given a polynomial time approximation scheme for packing, we show that geometric dispersion problems cannot be approximated arbitrarily well in polynomial time, unless P=NP. We give a 2/3 approximation algorithm for one version of the geometric dispersion problem. This algorithm is strongly polynomial in the size of the input, i.e. its running time does not depend on the area of P. We also discuss extensions and open problems.