PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 51-88
DOI: https://doi.org/10.7151/dmgt.1158

FREQUENCY PLANNING AND RAMIFICATIONS
OF COLORING

Andreas Eisenblätter, Martin Grötschel  and  Arie M.C.A. Koster

Konrad-Zuse-Zentrum für Informationstechnik Berlin
Takustraße 7, D-14195 Berlin, Germany

Abstract

This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful.

The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue.

Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand vertices and range form rather sparse to almost complete.

Keywords: frequency assignment, graph coloring.

2000 Mathematics Subject Classification: 05-02, 05C90, 90-02, 05C15.

References

[1]	K.I. Aardal, A. Hipolito, C.P.M. van Hoesel and B. Jansen, A branch-and-cut algorithm for the frequency assignment problem, Research Memorandum 96/011 (Maastricht University, 1996). Available at http://www.unimaas.nl/~svhoesel/.
[2]	K.I. Aardal, C.P.M. van Hoesel, A.M.C.A. Koster, C. Mannino and A. Sassano, Models and solution techniques for frequency assignment problems, ZIB Report 01-40 (Konrad-Zuse-Zentrum, Berlin, 2001). Available at http://www.zib.de/PaperWeb/abstracts/ZR-01-40.
[3]	K.I. Aardal, C.A.J. Hurkens, J.K. Lenstra and S.R. Tiourine, Algorithms for frequency assignment: the CALMA project, to appear in Operations Research.
[4]	S.M. Allen, D.H. Smith and S. Hurley, Lower bounding techniques for frequency assignment, Discrete Math. 197/198 (1999) 41-52.
[5]	L.G. Anderson, A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system, IEEE Transactions on Communications 21 (1973) 1294-1301, doi: 10.1109/TCOM.1973.1091583.
[6]	D. Applegate, R. Bixby, V. Chvátal and W. Cook, On the solution of traveling salesman problems, in: Proceedings of the International Congress of Mathematicians Berlin 1998, volume III of Documenta Mathematica, DMV, 1998.
[7]	G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and Approximation: combinatorial optimization problems and their approximability properties (Springer-Verlag, 1999).
[8]	M. Bellare, O. Goldreich and M. Sudan, Free bits, pcps and non-approximability-towards tight results, SIAM Journal on Computing 27 (1998) 804-915, doi: 10.1137/S0097539796302531.
[9]	H.P. van Benthem, GRAPH generating radio link frequency assignment problems heuristically (Master's thesis, Delft University of Technology, 1995).
[10]	M. Biró, M. Hujter and Zs. Tuza, Precoloring extension. I: interval graphs, Discrete Math. 100 (1992) 267-279, doi: 10.1016/0012-365X(92)90646-W.
[11]	R. Borndörfer, A. Eisenblätter, M. Grötschel and A. Martin, Frequency assignment in cellular phone networks, Annals of Operations Research 76 (1998) 73-93, doi: 10.1023/A:1018908907763.
[12]	F. Box, A heuristic technique for assigning frequencies to mobile radio nets, IEEE Transactions on Vehicular Technology 27 (1978) 57-74, doi: 10.1109/T-VT.1978.23724.
[13]	D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM 22 (1979) 251-256, doi: 10.1145/359094.359101.
[14]	S. Burer, R.D.C. Monteiro and Y. Zhang, Interior-point algorithms for semidefinite programming based on a nonlinear programming formulation, Technical Report TR 99-27, Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005, Dec. 1999.
[15]	A. Caminada, CNET France Telecom frequency assignment benchmark, URL: http://www.cs.cf.ac.uk/User/Steve.Hurley/f_bench.htm, 2000.
[16]	K.-N. Chang and S. Kim, Channel allocation in cellular radio networks, Computers and Operations Research 24 (1997) 849-860, doi: 10.1016/S0305-0548(96)00098-6.
[17]	D. Costa, On the use of some known methods for t-colourings of graphs, Annals of Operations Research 41 (1993) 343-358, doi: 10.1007/BF02023000.
[18]	M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assignment problem, Congr. Numer. 35 (1982) 191-208.
[19]	G. Dueck and T. Scheuer, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, J. Computational Physics (1990) 161-175, doi: 10.1016/0021-9991(90)90201-B.
[20]	A. Eisenblätter, Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds (Cuvillier Verlag, 2001).
[21]	A. Eisenblätter and A.M.C.A, Koster, FAP web-A website devoted to frequency assignment, URL: http://fap.zib.de, 2000.
[22]	P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157.
[23]	M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur and E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, European Journal of Operational Research 123 (2000) 241-255, doi: 10.1016/S0377-2217(99)00254-4.
[24]	A. Frieze and M. Jerrum, Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION, Algorithmica 18 (1997) 67-81, doi: 10.1007/BF02523688.
[25]	M. Grötschel, L. Lovász and A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Math. 21 (1984) 325-356.
[26]	M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, 1988).
[27]	W.K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.
[28]	M. Hellebrandt and H. Heller, A new heuristic method for frequency assignment, Technical Report TD(00) 003, COST 259 (Valencia, Spain, Jan, 2000).
[29]	C. Helmberg, SBmethod - A C++ implementation of the spectral bundle method, manuel to version 1,1, Technical Report 00-35, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) (Berlin, Germany, 2000).
[30]	C. Helmberg, Semidefinite programming for combinatorial optimization, Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) (Berlin, Germany, 2000), Habilitation TU Berlin.
[31]	S. Hurley, D.H. Smith and S.U. Thiel, FASoft: A system for discrete channel frequency assignment, Radio Science 32 (1997) 1921-1939, doi: 10.1029/97RS01866.
[32]	J. Janssen and K. Kilakos, Polyhedral analysis of channel assignment problems: (i) tours, Technical Report CDAM-96-17 (London School of Economics, 1996).
[33]	J. Janssen and K. Kilakos, An optimal solution to the ``Philadelphia'' channel assignment problem, IEEE Transactions on Vehicular Technology 48 (3) (1999) 1012-1014, doi: 10.1109/25.765037.
[34]	B. Jaumard, O. Marcotte and C. Meyer, Mathematical models and exact methods for channel assignment in cellular networks, in: B. Sansáo and P. Soriano, eds, Telecommunications Network Planning, Chapter 13 (Kluwer Academic Publishers, Boston, 1999) 239-255, doi: 10.1007/978-1-4615-5087-7_13.
[35]	D.S. Johnson, Worst case behaviour of graph colouring algorithms, Congr. Numer. 10 (1974) 513-527.
[36]	M. Jünger, G. Reinelt and G. Rinaldi, Network Models, Volume 7 of Handbooks in Operations Research and Management Science, Chapter The travelling salesman problem (Elsevier Science B.V., 1995) 225-330.
[37]	D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM 45 (2) (1998) 246-265, doi: 10.1145/274787.274791.
[38]	M. Karoński, Random graphs, in: R. Graham, M. Grötschel and L. Lovász, eds, Handbook of Combinatorics, Volume 1, Chapter 6 (Elsevier Science B.V., 1995) 351-380.
[39]	R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds, Complexity of Computer Computations (Plenum Press, New York, 1972) 85-103.
[40]	A.W.J. Kolen, A genetic algorithm for frequency assignment, (Technical report, Maastricht University, 1999). Available at http://www.unimaas.nl/~akolen/.
[41]	A.M.C.A. Koster, Frequency Assignment-Models and Algorithms (PhD Thesis, Maastricht University, 1999). Available at http://www.zib.de/koster/thesis.html.
[42]	A.M.C.A, Koster, C.P.M. van Hoesel and A.W.J. Kolen, Lower bounds for minimum interference frequency assignment problems, Technical Report RM 99/026 (Maastricht University, 1999). Available at http://www.zib.de/koster/.
[43]	R. Mathar and J. Mattfeldt, Channel assignment in cellular radio networks, IEEE Transactions on Vehicular Technology 42 (1993) 647-656, doi: 10.1109/25.260746.
[44]	B.H. Metzger, Spectrum management technique, Fall 1970, Presentation at 38th National ORSA meeting (Detroit, MI).
[45]	R.A. Murphey, P.M. Pardalos and M.G.C. Resende, Frequency assignment problems, in: D.-Z. Du and P.M. Pardalos, eds, Handbook of combinatorial optimization, volume Supplement Volume A (Kluwer Academic Publishers, 1999).
[46]	A. Raychaudhuri, Intersection Assignments, T-Colourings and Powers of Graphs (PhD Thesis, Rutgers University, 1985).
[47]	ROADEF challenge 2001. URL: http://www.prism.uvsq.fr/~ vdc/ROADEF/ CHALLENGES/2001/, 2000.
[48]	F.S. Roberts, On the mobile radio frequency assignment problem and the traffic light phasing problem, Annals of New York Academy of Sciences 319 (1979) 466-483, doi: 10.1111/j.1749-6632.1979.tb32824.x.
[49]	F.S. Roberts, T-colorings of graphs: Recent results and open problems, Discrete Math. 93 (1991) 229-245, doi: 10.1016/0012-365X(91)90258-4.
[50]	K.N. Sivarajan, R.J. McEliece and J.W. Ketchum, Channel assignment in cellular radio, in: Proceedings of the 39th IEEE Vehicular Technology Conference (1989) 846-850, doi: 10.1109/VETEC.1989.40173.
[51]	S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory 20 (B) (1976) 185-203.
[52]	J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Technical report, Communications Research Laboratory (McMaster University, Hamilton, Canada, 1998). Available at: http://www.unimaas.nl/~ sturm/.
[53]	B.A. Tesman, T-colorings, list T-colorings, and set T-colorings of graphs (PhD Thesis, Department of Mathematics, Rutgers University, 1989).
[54]	B.A. Tesman, Set T-colorings, Congr. Numer. 77 (1990) 229-242.
[55]	B.A. Tesman, List T-colorings, Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G.
[56]	B. Toft, Colouring, stable sets and perfect graphs, in: R. Graham, M. Grötschel and L. Lovász, eds, Handbook of Combinatorics, Volume 1, Chapter 4 (Elsevier Science B.V., 1995) 233-288.
[57]	C. Valenzuela, S. Hurley and D.H. Smith, A permutation based genetic algorithm for minimum span frequency assignment, Lecture Notes in Computer Science 1498 (1998) 907-916, doi: 10.1007/BFb0056932.
[58]	V.G. Vizing, Critical graphs with given chromatic class (Russian), Diskret, Analiz 5 (1965) 9-17.
[59]	W. Wang and C.K. Rushforth, An adaptive local-search algorithm for the channel-assignment problem (CAP), IEEE Transactions on Vehicular Technology 45 (1996) 459-466, doi: 10.1109/25.533761.
[60]	J.A. Zoellner and C.L. Beall, A breakthrough in spectrum conserving frequency assignment technology, IEEE Transactions on Electromagnetic Compatiblity 19 (1977) 313-319, doi: 10.1109/TEMC.1977.303601.

Received 4 January 2001
Revised 7 June 2001