Frequency Assignment in Cellular Phone Networks

Please always quote using this URN: urn:nbn:de:0297-zib-3044
  • We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Ralf Borndörfer, Andreas Eisenblätter, Martin Grötschel, Alexander Martin
Document Type:ZIB-Report
Date of first Publication:1997/07/11
Series (Serial Number):ZIB-Report (SC-97-35)
Published in:Appeared in: Annals of OR 76 (1998), 73-93