A Frequency Assignment Problem in Cellular Phone Networks
Please always quote using this URN: urn:nbn:de:0297-zib-2965
- We present a mathematical formulation of a \emph{frequency assignment problem} encountered in cellular phone networks: frequencies have to be assigned to stationary transceivers (carriers) such that as little interference as possible is induced while obeying several technical and legal restrictions. The optimization problem is NP-hard, and no good approximation can be guaranteed---unless P = NP. We sketch some starting and improvement heuristics, and report on their successful application for solving the frequency assignment problem under consideration. Computational results on real-world instances with up to 2877 carriers and 50 frequencies are presented.
Author: | Andreas Eisenblätter |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1997/06/20 |
Series (Serial Number): | ZIB-Report (SC-97-27) |
ZIB-Reportnumber: | SC-97-27 |
Published in: | Appeared in: Network design: connectivity and facilities location. P. M. Pardalos, D. Du (eds.) Providence, RI: American Mathematical Society 1998. DIMACS series in discrete mathematics and theoretical computer science, 40. Pp. 109-115 |