| SC 97-27 | Andreas Eisenblätter
A Frequency Assignment Problem in Cellular Phone Networks 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 |   |
Abstract: We present a mathematical formulation of a 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.