#
39 KAM Mathematical Colloquium

##
Prof. MARTIN GROETSCHEL

###
Konrad-Zuse-Centrum fuer Informationstechnik and Technische Universitaet
Berlin

##
FREQUENCY ASSIGNMENT IN MOBILE PHONE SYSTEMS

February 1, 2001
Lecture Room S4, Charles University, Malostranske nam. 25, Praha
1
14:00 PM

##
Abstract

In 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?
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.