Improving heuristics for the frequency assignment problem

Lower bounds for the frequency assignment problem can be found from maximal cliques and subgraphs related to cliques. In this paper we show that for many types of problem optimal assignments can be found by a process of assigning these subgraphs first, fixing the assignment and then extending the assignment to the full problem. We demonstrate the advantages of the method for some typical examples. In particular we give the first optimal assignments of several variants of the ‘Philadelphia’ problems. These problems have been used by several authors to assess assignment methods and lower bounds.