ECCC-Report TR06-030https://eccc.weizmann.ac.il/report/2006/030Comments and Revisions published for TR06-030en-usMon, 06 Mar 2006 16:46:27 +0200
Paper TR06-030
| Packing to angles and sectors |
Piotr Berman,
Jieun Jeong,
Shiva Prasad Kasiviswanathan,
Bhuvan Urgaonkar
https://eccc.weizmann.ac.il/report/2006/030In 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.
Mon, 06 Mar 2006 16:46:27 +0200https://eccc.weizmann.ac.il/report/2006/030