Domination analysis of greedy heuristics for the frequency assignment problem

We introduce the greedy expectation algorithm for the fixed spectrum version of the frequency assignment problem. This algorithm was previously studied for the travelling salesman problem. We show that the domination number of this algorithm is at least sigma(n-[log2 n]-1), where sigma is the available span and n the number of vertices in the constraint graph. In contrast to this we show that the standard greedy algorithm has domination number strictly less than sigma(n)e(-5(n-1)/144) for large n and fixed sigma. (C) 2003 Elsevier B.V. All rights reserved.