Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 1-12 |
| Seitenumfang | 12 |
| Fachzeitschrift | Discrete applied mathematics |
| Jahrgang | 148 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Diskrete Mathematik und Kombinatorik
- Mathematik (insg.)
- Angewandte Mathematik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Discrete applied mathematics, Jahrgang 148, Nr. 1, 30.04.2005, S. 1-12.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -