Using Lower Bounds in Minimum Span Frequency Assignment

The frequency assignment problem is an important NP-hard problem which involves the assignment of frequencies to a set of transmitters in such a way that certain constraints, defining the frequency separation needed between pairs of transmitters, are satisfied. In this paper we show that good assignments can be found if assignment algorithms assign a subset of the constraints initially. This partial assignment is then used as a starting assignment for the solution of the whole problem. Good results can be found if the subset chosen for the initial assignment corresponds to the subset that produces good lower bounds.