Local search algorithms for the radio link frequency assignment problem

Radio link frequency assignment problems arise in practice when a network of radio links has to be established. Each radio link has to be assigned an operating frequency. The frequency assignments have to comply with certain regulations and physical characteristics of the transmitters. The interference level between frequencies assigned to different links has to be small, since otherwise communication will be distorted. Two objectives are considered: the total interference costs and, in case of no interference, the frequency spectrum usage. We develop several approximation algorithms for the problem and compare their performance on some practical instances. We also develop a lower bounding technique based on a nonlinear relaxation in order to estimate the quality of the approximate solutions for some of these instances.