Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-030 | 17th January 2006 00:00

Packing to angles and sectors

RSS-Feed




TR06-030
Authors: Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar
Publication: 6th March 2006 16:46
Downloads: 776
Keywords: 


Abstract:

In our problem we are given a set of customers, their positions on the
plane and their demands. Geometrically, directional antenna with
parameters $\alpha,\rho,R$ is a set
of points with radial coordinates $(\theta,r)$ such that
$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of
possible directional antennas we want to cover all customers positions
so that the demands of customers assigned to an antenna stay within
a bound. We provide approximation algorithms for three versions
of this cover problem.



ISSN 1433-8092 | Imprint