In the early days of mobile telephony this channel assignment problem was modelled as an (ordinary) graph colouring problem, and colouring algorithms were used to solve it. Practical experience revealed that these solutions have a number of deficiencies.
A detailed analysis of this problem showed that a better 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, 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.
This lecture is based on efforts of the ZIB telecommunications research
group, in particular the work of Andreas Eisenblaetter and Arie Koster.