Measuring the effectiveness of frequency assignment algorithms

Lower bounds are used to assess the quality of frequency assignments and the effectiveness of the algorithms used to obtain them. This paper makes three contributions. First, a technique is described for modifying an effective existing lower bound for the span to take account of multiple interference. Multiple interference may increase the span and the modification captures some or all of this increase. Second, new results are given for a lower bound for some of the two level penalty-based COST259 problems. It remains true that for these problems, the gap between upper and lower bounds is large, by comparison with other benchmarks. Third, some evidence is presented to suggest that the assignments available today for problems of the COST259 type are still capable of very significant improvement.