Frequency planning and ramifications of coloring

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

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 51-88
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Andreas Eisenblätter, Martin Grötschel, and Arie M.C.A. Koster. "Frequency planning and ramifications of coloring." Discussiones Mathematicae Graph Theory 22.1 (2002): 51-88. <http://eudml.org/doc/270645>.

@article{AndreasEisenblätter2002,
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.},
author = {Andreas Eisenblätter, Martin Grötschel, Arie M.C.A. Koster},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {frequency assignment; graph coloring; span of coloring},
language = {eng},
number = {1},
pages = {51-88},
title = {Frequency planning and ramifications of coloring},
url = {http://eudml.org/doc/270645},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Andreas Eisenblätter
AU - Martin Grötschel
AU - Arie M.C.A. Koster
TI - Frequency planning and ramifications of coloring
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 51
EP - 88
AB - 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.
LA - eng
KW - frequency assignment; graph coloring; span of coloring
UR - http://eudml.org/doc/270645
ER -

References

top
  1. [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. [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. Zbl1157.90005
  3. [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. Zbl1163.90579
  4. [4] S.M. Allen, D.H. Smith and S. Hurley, Lower bounding techniques for frequency assignment, Discrete Math. 197/198 (1999) 41-52 Zbl0956.90057
  5. [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. [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. Zbl0904.90165
  7. [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). Zbl0937.68002
  8. [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. Zbl0912.68041
  9. [9] H.P. van Benthem, GRAPH generating radio link frequency assignment problems heuristically (Master's thesis, Delft University of Technology, 1995). 
  10. [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. [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. Zbl0895.90090
  12. [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. [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. Zbl0394.05022
  14. [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. Zbl1006.90060
  15. [15] A. Caminada, CNET France Telecom frequency assignment benchmark, URL: http://www.cs.cf.ac.uk/User/Steve.Hurley/f_bench.htm, 2000 
  16. [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. Zbl0891.90166
  17. [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. Zbl0771.68089
  18. [18] M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assignment problem, Congr. Numer. 35 (1982) 191-208. 
  19. [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. Zbl0707.65039
  20. [20] A. Eisenblätter, Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds (Cuvillier Verlag, 2001). 
  21. [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. [22] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157. 
  23. [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. Zbl0961.90051
  24. [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. Zbl0873.68078
  25. [25] M. Grötschel, L. Lovász and A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Math. 21 (1984) 325-356. 
  26. [26] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, 1988). Zbl0634.05001
  27. [27] W.K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899. 
  28. [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. [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. [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. [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. [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. [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. [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₁3. 
  35. [35] D.S. Johnson, Worst case behaviour of graph colouring algorithms, Congr. Numer. 10 (1974) 513-527. 
  36. [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. Zbl0832.90118
  37. [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. Zbl0904.68116
  38. [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. Zbl0845.05082
  39. [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. [40] A.W.J. Kolen, A genetic algorithm for frequency assignment, (Technical report, Maastricht University, 1999). Available at http://www.unimaas.nl/~akolen/. 
  41. [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. [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. [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. [44] B.H. Metzger, Spectrum management technique, Fall 1970, Presentation at 38th National ORSA meeting (Detroit, MI). 
  45. [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). Zbl1253.90137
  46. [46] A. Raychaudhuri, Intersection Assignments, T-Colourings and Powers of Graphs (PhD Thesis, Rutgers University, 1985). 
  47. [47] ROADEF challenge 2001. URL: http://www.prism.uvsq.fr/~ vdc/ROADEF/ CHALLENGES/2001/, 2000. 
  48. [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. Zbl0475.94021
  49. [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. Zbl0751.05042
  50. [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. [51] S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory 20 (B) (1976) 185-203. Zbl0293.05115
  52. [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. [53] B.A. Tesman, T-colorings, list T-colorings, and set T-colorings of graphs (PhD Thesis, Department of Mathematics, Rutgers University, 1989). 
  54. [54] B.A. Tesman, Set T-colorings, Congr. Numer. 77 (1990) 229-242. 
  55. [55] B.A. Tesman, List T-colorings, Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G. 
  56. [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. Zbl0844.05042
  57. [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. [58] V.G. Vizing, Critical graphs with given chromatic class (Russian), Diskret, Analiz 5 (1965) 9-17. 
  59. [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. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.