zbMATH — the first resource for mathematics

Improving heuristics for the frequency assignment problem. (English) Zbl 0943.90056
Summary: Lower bounds for the frequency assignment problem can be found from maximal cliques and subgraphs related to cliques. In this paper we show that for many types of problem optimal assignments can be found by a process of assigning these subgraphs first, fixing the assignment and then extending the assignment to the full problem. We demonstrate the advantages of the method for some typical examples. In particular, we give the first optimal assignments of several variants of the “Philadelphia” problems. These problems have been used by several authors to assess assignment methods and lower bounds.

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI
[1] 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
[2] Castelino, D.J.; Hurley, S.; Stephens, N.M., A tabu search algorithm for frequency assignment, Annals of operations research, 63, 301-319, (1996) · Zbl 0851.90094
[3] Costa, D., On the use of some known methods for tcolourings of graphs, Annals of operations research, 41, 343-358, (1993) · Zbl 0771.68089
[4] Crompton, W.; Hurley, S.; Stephens, N.M., A parallel genetic algorithm for frequency assignment problems, (), 81-84
[5] Gamst, A., Homogeneous distribution of frequencies in a regular hexagonal cell system, IEEE transactions on vehicular technology, 31, 132-144, (1982)
[6] R. Leese, A unified approach to the assignment of radio channels on a regular hexagonal grid, IEEE Transactions on Vehicular Technology to appear. · Zbl 0868.94004
[7] Gamst, A., Some lower bounds for a class of frequency assignment problems, IEEE transactions on vehicular technology, 35, 8-14, (1986)
[8] Smith, D.H.; Hurley, S., Bounds for the frequency assignment problem, Discrete mathematics, 167, 168, 571-582, (1997) · Zbl 0873.05041
[9] Hale, W.K., Frequency assignment: theory and applications, (), 1497-1514
[10] Roberts, F.S., T-colorings of graphs: recent results and open problems, Discrete mathematics, 93, 229-245, (1991) · Zbl 0751.05042
[11] Zoellner, J.A.; Beall, C.L., A breakthrough in spectrum conserving frequency assignment technology, IEEE trans. on electromagnetic compatibility, EMC-19, 313-319, (1977)
[12] Prim, R.C., Shortest connection networks and some generalizations, Bell system technical journal, 36, 1389-1401, (1957)
[13] Janssen, J.; Kilakos, K., Polyhedral analysis of channel assignment problems: (I) tours, ()
[14] Descartes, B., Solution to advanced problem number 4526, Amer. math. monthly, 61, 352, (1954)
[15] Mycielski, J., Sur le coloriage des graphs, Colloq. math., 3, 161-162, (1955) · Zbl 0064.17805
[16] Hurley, S.; Smith, D.H.; Thiel, S.U., Fasoft: A software system for discrete channel frequency assignment, radio science · Zbl 0943.90056
[17] Prosser, P., Hybrid algorithms for the constraint satisfaction problem, Computational intelligence, 9, 3, 268-299, (1993)
[18] Hale, W.K., New spectrum management tools, (), 47-53
[19] CELAR Data, ftp://ftp.cs.city.ac.uk/pub/constraints/cspbenchmarks
[20] Carraghan, R.; Pardalos, P.M., An exact algorithm for the maximum clique problem, Operations research letters, 9, 375-382, (1990) · Zbl 0711.90080
[21] Gendreau, M.; Soriano, P.; Salvail, L., Solving the maximum clique problem using a tabu search approach, Annals of operations research, 41, 385-403, (1993) · Zbl 0775.90297
[22] Volgenant, T.; Jonker, R., A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, European journal of operational research, 9, 83-89, (1982) · Zbl 0471.90088
[23] ORSEP/contents.html ftp://www.mathematik.uni-kl.de/ pub/Math/ORSEPNOLGENAN.ZIP
[24] Anderson, L.G., A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system, IEEE transactions on communications, 21, 1294-1301, (1973)
[25] Sivarajan, K.N.; McEliece, R.J.; Ketchum, J.W., Channel assignment in cellular radio, (), 846-859
[26] Wang, W.; Rushforth, C.K., An adaptive local-search algorithm for the channel-assignment problem (CAP), IEEE trans. on vehicular technology, 45, 459-466, (1996)
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.