Generation of lower bounds for minimum span frequency assignment

Allen, Stuart Michael ORCID: https://orcid.org/0000-0003-1776-7489, Smith, Derek H. and Hurley, Stephen 2002. Generation of lower bounds for minimum span frequency assignment. Discrete applied mathematics 119 (1-2) , pp. 59-78. 10.1016/S0166-218X(01)00265-7

Full text not available from this repository.

Abstract

Minimum span frequency assignment problems require lower bounds for the span in order to assess the quality of individual assignments, and to effectively compare different meta-heuristic algorithms. The generation of good lower bounds requires the identification of critical subproblems. These subproblems are subgraphs of a constraint graph. Sometimes clique subgraphs lead to good lower bounds. However for some problems the clique must be modified in order to obtain the best possible bound. This can be time consuming, requires manual intervention and is dependent on the initial clique obtained and the specific problem. For practical use, a simple bounding technique is needed that can be universally applied to all problems without modification. Two algorithms based on meta-heuristics are presented that aim to find a subproblem that gives the best possible lower bound. This avoids the need for clique detection routines and manual intervention, and gives a robust and automatic method for generating lower bounds for all minimum span problems. These algorithms use mathematical programming formulations of the frequency assignment problem. Extensive testing on a wide range of problems shows that bounds from the new algorithms match those using previous techniques, and in some cases are significantly better.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics Systems Immunity Research Institute (SIURI)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics
Uncontrolled Keywords:	Radio frequency assignment; Lower bounds; Subgraphs
Publisher:	Elsevier
ISSN:	0166-218X
Last Modified:	17 Oct 2022 09:00
URI:	https://orca.cardiff.ac.uk/id/eprint/1807

Citation Data

Cited 7 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item