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.