zbMATH — the first resource for mathematics

Generation of lower bounds for minimum span frequency assignment. (English) Zbl 1102.90372
Summary: 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.

90C35 Programming involving graphs or networks
68W40 Analysis of algorithms
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI
[1] S.M. Allen, Frequency assignment problems: subgraph generation for lower bounds, Technical Report UG-M-98-2, Division of Mathematics and Computing, University of Glamorgan, December 1998.
[2] Allen, S.M.; Smith, D.H.; Hurley, S., Lower bounding techniques for frequency assignment, Discrete math., 197/198, 41-52, (1999) · Zbl 0956.90057
[3] Carraghan, R.; Pardalos, P., An exact algorithm for the maximum clique problem, Oper. res. lett., 9, 375-382, (1990) · Zbl 0711.90080
[4] S. Hurley, D.H. Smith, Meta-heuristics and channel assignment, in: R. Leese (Ed.), Methods and Algorithms for Radio Channel Assignment, Oxford University Press, Oxford, to appear.
[5] Hurley, S.; Smith, D.H.; Thiel, S.U., Fasoft: A system for discrete channel frequency assignment, Radio sci., 32, 1921-1939, (1997)
[6] Pekny, J.F.; Miller, D.L., A staged primal-dual algorithm for finding a minimum cost perfect two-matching in an undirected graph, ORSA J. comput., 6, 68-81, (1994) · Zbl 0798.90128
[7] A. Raychaudhuri, Intersection assignments, T-colourings and powers of graphs, Ph.D. Thesis, Rutgers University, 1985.
[8] Smith, D.H.; Hurley, S., Bounds for the frequency assignment problem, Discrete math., 167/168, 571-582, (1997) · Zbl 0873.05041
[9] D.H. Smith, S. Hurley, S.M. Allen, A new lower bound for the channel assignment problem, IEEE Trans. Vehicular Technol. 49 (4) 1265-1272.
[10] D.H. Smith, S. Hurley, S.M. Allen, in: R. Leese (Ed.), Lower bounds for channel assignment, Methods and Algorithms for Radio Channel Assignment, Oxford University Press, Oxford, to appear.
[11] Smith, D.H.; Hurley, S.; Thiel, S.U., Improving heuristics for the frequency assignment problem, European J. oper. res., 107, 76-86, (1998) · Zbl 0943.90056
[12] Tcha, D-w.; Chung, Y-j.; Choi, T-j., A new lower bound for the frequency assignment problem, IEEE/ACM trans. networking, 5, 34-39, (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.