Frequency assignment in cellular phone networks

We present a graph-theoretic model for the 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.