zbMATH — the first resource for mathematics

Using lower bounds in minimum span frequency assignment. (English) Zbl 0970.90041
Voss, Stefan (ed.) et al., Meta-heuristics. Advances and trends in local search paradigms for optimization. 2nd Meta-Heuristics international conference (MIC-97), Sophia-Antipolis, France, July 21-24, 1997. Dordrecht: Kluwer Academic Publishers. 191-204 (1999).
Summary: The frequency assignment problem is an important NP-hard problem which involves the assignment of frequencies to a set of transmitters in such a way that certain constraints, defining the frequency separation needed between pairs of transmitters, are satisfied. In this paper we show that good assignments can be found if assignment algorithms assign a subset of the constraints initially. This partial assignment is then used as a starting assignment for the solution of the whole problem. Good results can be found if the subset chosen for the initial assignment corresponds to the subset that produces good lower bounds.
For the entire collection see [Zbl 0930.00082].

90B80 Discrete location and assignment