Upper and Lower Bounding Techniques for Frequency Assignment Problems

摘要

The authors consider two variants of the radio link frequency assignment problem.Each radio link has to be assigned a particular frequency. The interference level between the frequencies assigned to the different links has to be acceptable, since otherwise communication will be distorted. The authors develop several approximation algorithms for the problems, which are based on local search, and the authors 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.