Lower bounding techniques for frequency assignment.

*(English)*Zbl 0956.90057Summary: The frequency assignment problem is an NP complete problem of great importance to the radiocommunications industry. Most current solution techniques for real frequency assignment problems use heuristic algorithms to obtain suboptimal solutions in an acceptable time. By formulating the problems in terms of graph colourings, lower bounds can be obtained to assess the quality of these heuristic solutions.

Bounds based on the travelling salesman problem have proved to be successful, in some cases giving tight bounds when applied to a suitable subproblem. However, for general problems these bounds may be difficult to calcualte or are far from optimal. The choice of subproblem is critical in evaluating these bounds and can also be of use in the application of the heuristic algorithms. In this paper we present a number of new and improved techniques for determining lower bounds.

Bounds based on the travelling salesman problem have proved to be successful, in some cases giving tight bounds when applied to a suitable subproblem. However, for general problems these bounds may be difficult to calcualte or are far from optimal. The choice of subproblem is critical in evaluating these bounds and can also be of use in the application of the heuristic algorithms. In this paper we present a number of new and improved techniques for determining lower bounds.

##### MSC:

90C35 | Programming involving graphs or networks |

05C90 | Applications of graph theory |

90C27 | Combinatorial optimization |

##### Software:

FASoft
PDF
BibTeX
XML
Cite

\textit{S. M. Allen} et al., Discrete Math. 197--198, 41--52 (1999; Zbl 0956.90057)

Full Text:
DOI

##### References:

[1] | Beasley, J.E., Lagrangean relaxation, (), 243-303, Ch. 6 |

[2] | Bouju, A.; Boyce, J.F.; Dimitropoulos, C.H.D.; vom Scheidt, G.; Taylor, J.G., Tabu search for the radio links frequency assignment problem, (), 233-250 |

[3] | Costa, D., On the use of some known methods for T-colourings of graphs, Ann. oper. res., 41, 343-358, (1993) · Zbl 0771.68089 |

[4] | Fisher, M.L., The Lagrangean relaxation method for solving integer programming problems, Management sci., 27, 1, 1-18, (1981) · Zbl 0466.90054 |

[5] | Hale, W.K., Frequency assignment: theory and applications, (), 1497-1514 |

[6] | Hurley, S.; Smith, D.H.; Thiel, S.U., Fasoft: a system for discrete channel frequency assignment, Radio sci., 32, 5, 1921-1939, (1997) |

[7] | Johnson, D.S.; McGeoch, L.A.; Rothberg, E.E., Asymptotic experimental analysis for the held-karp traveling salesman bound, (), 341-350 · Zbl 0845.90123 |

[8] | 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, 1, 68-81, (1994) · Zbl 0798.90128 |

[9] | Prim, R.C., Shortest connection networks and some generalizations, Bell system tech. J., 36, 1389-1401, (1997) |

[10] | Raychaudhuri, A., Intersection assignments, T-colourings and powers of graphs, () |

[11] | Smith, D.H.; Hurley, S., Bounds for the frequency assignment problem, Discrete math., 167/168, 571-582, (1997) · Zbl 0873.05041 |

[12] | 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 |

[13] | Volgenant, A., Symmetric traveling salesman problems, European J. oper. res., 49, 153-154, (1990), ftp://www.mathematik.uni-kl.de/pub/Math/ORSEP/VOLGENAN.ZIP · Zbl 1403.90008 |

[14] | Volgenant, T.; Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European J. oper. res., 9, 83-89, (1982) · Zbl 0471.90088 |

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.