Colouring Radio Waves

Graph theory was - to a large extent - developed along attempts to solve the four-colour-problem. Already in the early days of radio communication, it was noticed that colouring theory can not only be employed to paint maps but also to make good use of radio channels.

In modern GMS mobile telecommunication systems a large number of communication links have to be established with a limited number of available frequencies (or channels). How should the channels be assigned to the transceivers so that the customers receive high quality service?

A detailed analysis of this problem shows that a proper way to formulate the channel assignment problem is the following: Obeying several technical and legal restrictions, channels have to be assigned to transceivers so that interference is as small as possible. It turns out that this problem can be considered as a list coloring problem with additional side constraints.

I will present several formulations of this problem as integer linear programs, and relate these to standard colouring theory. I will outline a relaxation that leads to a semidefinite program, and I will discuss heuristic and exact algorithms for its solution. Computational results for channel assignment problems of a German cellular phone network operator will be presented.

I will also say a few words about the radio interface of the new UMTS technology which is not too well understood at present.

This lecture is based on efforts of the ZIB telecommunications research group, in particular the work of Andreas Eisenblätter and Arie Koster.