The operators of cellular phone networks are allowed to use a portion of the electro-magnetic radio spectrum for the radio communication with cellular phones. Networks operating according to the GSM standard use, among others, a frequency division multiple access scheme. The available portion of the radio spectrum is partitioned into slots of equal size, called channels. Radio links to cellular phones are established via stationary transceivers. Each transceiver uses a fixed channel, whereas cellular phones tune to the channel of the transceiver via which they are communicating.

A central problem in radio communication is that the signals of transceivers (and cellular phones) may be subject to interference. Interference usually comes from a near-by transceiver transmitting at the same or an adjacent channel. In practice, the number of transceivers in a cellular phone network exceeds the number of available channels by a factor of 30 or more. Thus, channels have to be reused often. Elaborate interference predictions are performed to determine for which pairs of transceivers the use of the same channel or adjacent channels would lead to interference.

This project ended after almost 6 years. At first, we concentrated on the development of algorithms for the automatic generation of frequency-plans. The research was centered on the design and implementation of primal heuristics that minimize the interference. Substantial improvements could be achieved in comparison with previously used techniques [Ei01]. Some of the developed techniques have been in at E-Plus for years. In addition, the E-Plus licensed Cosiro to integrate the software in their radio interface planning tool Fun.

Like in 2000, in 2001 we focussed on methods for the computation of unavoidable interference. Together with Christoph Helmberg (Technical University of Chemnitz), we developed a method based on the solution of a semidefinte relaxation for the k-partition problem [Ei02]. This method provided the best lower bound achieved so far for the unavoidable co-channel interference. The results show that around half the interference that appears in the best frequency plans cannot be avoided. It can be shown that in most cases both lower and upper bound have to be improved further to close the gap between them. So far, such improvement could only be achieved by the use of significant computer power and computing time.

The internet server FAP web is operated since year 2000. Besides a description of frequency assignment problems, cf. [AaHoKoMaSa03], the server provides also practical test instances for research purposes. These are partly provided by the EU-sponsored COST-259 project [Co01]. These instances have been made available to the public via our server for the first time. Finally, an annotated bibliography on frequency assignment problems have been added to FAP web.

• K. I. Aardal, C. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino, A. Sassano. Models and Solution Techniques for the Frequency Assignment Problem. 4OR, 1(4):261–317, 2003.
• R. Borndörfer, A. Eisenblätter, M. Grötschel, A. Martin. Frequency Assignment in Cellular Phone Networks. Annals of Operations Research, 76:73–93, 1998.
• Wireless Flexible Personalized Communications - COST 259: European Co-operation in Mobile Radio Research. John Wiley & Sons, , 2001. COST Action 259–-Final Report
• A. Eisenblätter. Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. Dissertationsschrift, Technische Universität Berlin, 2001.
• Andreas Eisenblätter. The Semidefinite Relaxation of the k-Partition Polytope is Strong. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO'02), volume 2337of Lecture Notes in Computer Science, pp. 273–290, Berlin Heidelberg, 2002.
• A. Eisenblätter. Assigning Frequencies in GSM Networks. In: Operations Research Proceedings 2002, pp. 33–40, 2003. Selected Papers of the International Conference on Operations Research (SOR 2002), Klagenfurt, September 2 - 5, 2002
• Eisenblätter, A., Grötschel, M., Koster, A. M. C. A.. Frequency Assignment and Ramifications of Coloring. Discussiones Mathematicae Graph Theory, 22:51–88, 2002.
• Eisenblätter, A., Kürner, T., Fauß. Radio Planning Algorithms for Interference Reduction in Cellular Networks. In: Communications for the Millennium. COST 252/259 Joint Workshop, University of Bradford, 21–22 apr 1998., pp. 87–92, 1998.

• Participation in the EU project COST 259 within the COST framework
• Chairman of COST 259 subworking group 3.1

• Frequenzzuweisung im Mobilfunk (in German) JPEG, Postscript