Range assignment of base-stations maximizing coverage area without interference

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ACHARYYA Ankush DE Minati NANDY Subhas Chandra ROY Bodhayan

Year of publication 2020
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web
Doi http://dx.doi.org/10.1016/j.tcs.2019.10.044
Keywords Quadratic programming; Discrete packing; Range assignment in wireless communication; NP-hardness; Approximation algorithm; PTAS
Description We study the problem of assigning non-overlapping geometric objects centered at a given set of points such that the sum of area covered by them is maximized. The problem remains open since 2002, as mentioned in a lecture slide of David Eppstein. In this paper, we have performed an exhaustive study on the problem. We show that, if the points are placed in R-2 then the problem is NP-hard even for simplest type of covering objects like disks or squares. In contrast, Eppstein (2017) [10] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping disks when the points are arbitrarily placed in R-2. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in R-2 gives a 2-approximation solution for the sum of area maximization problem. We also propose a PTAS for the same problem. Our results can be extended in higher dimensions as well as for a class of centrally symmetric convex objects.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.