Upper and lower bounding techniques for frequency assignment problems

We consider two variants of the radio link frequency assignment problem??. These problems arise in practice when a network of radio links has to be established??. Each radio link has to be assigned a particular frequency??. The interference level between the frequencies assigned to the di??erent links has to be acceptable??, since otherwise communication will be distorted.?? The frequency assignments have to comply with certain regulations and physical characteristics of the transmitters.?? Moreover??, the number of frequencies is to be minimized, because each frequency used in the network has to be reserved at a certain cost??. We develop several approximation algorithms for the problems??, which are based on local search,?? and we compare their performance on some practical instances.?? Lower bounding techniques based on nonlinear programming and the chromatic number of a graph are used to estimate the quality of the approximate solutions for these instances??.