The frequency assignment problem arises when a large number of transmitters are operating in a region and the interference is to be minimized while using the spectrum efficiently. In this work, the minimum span version of the frequency assignment problem is reviewed. Since the frequency assignment problem is an NP-hard problem, lower bounding techniques play an important role both in the exact solution attempts and in determining the quality of the upper bounds. Existing algorithmic approaches are surveyed for the lower bounding techniques. Then two of the recently proposed approaches for cellular networks are analyzed in detail and empirically evaluated for their relative performance using both benchmark problems found in the literature and randomly generated instances. An integrated software, which is specifically developed for this purpose, is also presented.

Keywords: Minimum Span Frequency Assignment, Lower Bound, Cellular Networks, Clique, Linear Programming.