R.A. Murphey, P.M. Pardalos, and M.G.C. Resende
In Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, eds., Kluwer Academic Publishers, suppl. vol. A, pp. 295-377, 1999
ABSTRACT
The ever growing number of wireless communications
systems deployed around the globe have made the optimal assignment of a
limited radio frequency spectrum a problem of primary importance.
At issue are planning models for permanent spectrum allocation,
licensing, regulation, and network design. Further at issue are
on-line algorithms for dynamically assigning frequencies to users within
an established network. Applications include aeronautical mobile,
land mobile, maritime mobile, broadcast, land fixed (point-to-point),
and satellite systems. This paper surveys research conducted by
theoreticians, engineers, and computer scientists regarding the
frequency assignment problem (FAP) in all of its guises. The paper
begins by defining some of the more common types of FAPs. It
continues with a discussion on measures of optimality relating to the
use of spectrum, models of interference, and mathematical
representations of the many FAPs, both in graph theoretic terms, and as
mathematical programs. Graph theory and, in particular, graph
coloring play an important role in the FAP since, in many instances, the
FAP is cast in a form which closely resembles a graph coloring.
Theoretical results that bound optimal solutions for special FAP
structures are presented. Exact algorithms for general FAPs are
explained, and since many FAP instances are computationally hard, much
space is devoted to approximate algorithms. The paper concludes
with a review of evaluation methods for FAP algorithms, test problem
generators, and a discussion of the underlying engineering issues which
should be considered when generating test problems.