The complexity of base station positioning in cellular networks

Christian Glaßer, Steffen Reith, Heribert VollmerDiscret. Appl. Math 2005 · DOI · OpenReview

Abstract

We consider two optimization problems for cellular telephone networks, that arise in a recently discussed ITU proposal for a traffic load model. These problems address the positioning of base stations (on given possible locations) with the aim to maximize the number of supplied demand nodes and minimize the number of stations that have to be built. We show that these problems are hard to approximate, but their Euclidean versions allow a polynomial-time approximation scheme (PTAS). Furthermore, we consider other related optimization problems.
BibTeX
@article{glaer2005complexity,
  author = {Christian Glaßer and Steffen Reith and Heribert Vollmer},
  title = {{The complexity of base station positioning in cellular networks}},
  journal = {Discret. Appl. Math.},
  year = {2005},
  doi = {10.1016/j.dam.2004.07.005},
}

Loading related content...

Figure