or How to spread rumors without wearing out your voice or your shoes

Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 449-458, 2006.

Abstract:

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers and radii that cover a given set of demand points in the plane at the smallest possible cost. We consider cost functions of the form ∑_{j}rwhere_{j}^{α}ris the cost of transmission to radius^{α}r. Special cases arise for α=1 and α=2; power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers, which may be constrained to lie in a given discrete set, to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points on a given line in order to cover the demand points; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover the demand points; and (c) a polynomial-time approximation scheme for the problem of computing a

minimum cost covering tour, in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a path that connects the centers of the disks.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012