Details
| Original language | English |
|---|---|
| Pages (from-to) | 1-12 |
| Number of pages | 12 |
| Journal | Discrete applied mathematics |
| Volume | 148 |
| Issue number | 1 |
| Publication status | Published - 30 Apr 2005 |
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.
Keywords
- Approximation algorithms, Complexity, Demand Node, PTAS, Traffic load model
ASJC Scopus subject areas
- Mathematics(all)
- Discrete Mathematics and Combinatorics
- Mathematics(all)
- Applied Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Discrete applied mathematics, Vol. 148, No. 1, 30.04.2005, p. 1-12.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - The complexity of base station positioning in cellular networks
AU - Glaßer, Christian
AU - Reith, Steffen
AU - Vollmer, Heribert
PY - 2005/4/30
Y1 - 2005/4/30
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Complexity
KW - Demand Node
KW - PTAS
KW - Traffic load model
UR - http://www.scopus.com/inward/record.url?scp=15344349985&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2004.07.005
DO - 10.1016/j.dam.2004.07.005
M3 - Article
AN - SCOPUS:15344349985
VL - 148
SP - 1
EP - 12
JO - Discrete applied mathematics
JF - Discrete applied mathematics
SN - 0166-218X
IS - 1
ER -