×

zbMATH — the first resource for mathematics

Models and solution techniques for frequency assignment problems. (English) Zbl 1157.90005
Summary: Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, wireless LANs, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

MSC:
90B18 Communication networks in operations research
90B50 Management decision making, including multiple objectives
90C59 Approximation methods and heuristics in mathematical programming
90C30 Nonlinear programming
Software:
CALMA; FASoft; ToulBar2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aardal, K. I., Hipolito, A., van Hoesel, C. P. M., & Jansen, B. (1996). A branch-and-cut algorithm for the frequency assignment problem. Research Memorandum 96/011, Maastricht University.
[2] Aardal, K. I., Hurkens, C. A. J., Lenstra, J. K., & Tiourine, S. R. (2002). Algorithms for radio link frequency assignment: The CALMA project. Operations Research, 50(6), 968–980. · Zbl 1163.90579 · doi:10.1287/opre.50.6.968.353
[3] Aardal, K. I., van Hoesel, C. P. M., Koster, A. M. C. A., Mannino, C., & Sassano, A. (2003). Models and solution techniques for the frequency assignment problem. 4OR, 1(4), 261–317. · Zbl 1042.90049
[4] Abril, J., Comellas, F., Cortés, A., Ozón, J., & Vaquer, M. (2000). A multi-agent system for frequency assignment in cellular radio networks. IEEE Transactions on Vehicular Technology, 49(5), 1558–1565. · doi:10.1109/25.892539
[5] Adjakplé, P. M., & Jaumard, B. (1997). Greedy and tabu search heuristics for channel block assignment in cellular systems. Technical Report G-97-45, École Polytechnique de Montréal, July 1997.
[6] Al-Khaled, F. S. (1998). Optimal radio channel assignment through the new binary dynamic simulated annealing algorithm. International Journal of Communication Systems, 11, 327–336. · Zbl 1062.94542 · doi:10.1002/(SICI)1099-1131(199809/10)11:5<327::AID-DAC374>3.0.CO;2-9
[7] Allen, S. M., Smith, D. H., & Hurley, S. (1999). Lower bounding techniques for frequency assignment. Discrete Mathematics, 197–198, 41–52. · Zbl 0956.90057
[8] Allen, S. M., Dunkin, N., Hurley, S., & Smith, D. (1998). Frequency assignment problems: Benchmarks and lower bounds. Technical report, University of Glamorgan. URL http://www.glam.ac.uk/sotschool/doms/Research/Fap2last.pdf .
[9] Alouf, S., Altman, E., Galtier, J., Lalande, J.-F., & Touati, C. (2005). An algorithm for satellite bandwidth allocation. In Proceedings of IEEE infocom 2005 (Vol. 1, pp. 560–571).
[10] Anderson, L. G. (1973). A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system. IEEE Transactions on Communications, 21, 1294–1301. · doi:10.1109/TCOM.1973.1091583
[11] Avenali, A., Mannino, C., & Sassano, A. (2002). Minimizing the span of d-walks to compute optimum frequency assignments. Mathematical Programming, 91(2), 357–374. Previously published as technical report 04-00, DIS-Università di Roma ”La Sapienza”, Rome, Italy. · Zbl 1049.90012 · doi:10.1007/s101070100247
[12] Baybars, I. (1982). Optimal assignment of broadcasting frequencies. European Journal of Operations Research, 9, 257–263. · Zbl 0475.90091 · doi:10.1016/0377-2217(82)90033-9
[13] Beckmann, D., & Killat, U. (1999a). Frequency planning with respect to interference minimization in cellular radio networks. Technical Report TD(99) 032 COST 259, Vienna, Austria, January 1999.
[14] Beckmann, D., & Killat, U. (1999b). A new strategy for the application of genetic algorithms to the channel-assignment problem. IEEE Transactions on Vehicular Technology, 48(4), 1261–1269. July 1999. · doi:10.1109/25.775374
[15] Björklund, P., Värbrand, P., & Yuan, D. (2005). Optimal frequency planning in mobile networks with frequency hopping. Computers and Operations Research, 32, 169–186. · Zbl 1061.90013 · doi:10.1016/S0305-0548(03)00210-7
[16] Bodlaender, H. L. (1997). Treewidth: Algorithmic techniques and results. Lecture notes in computer science: Vol. 1295, Proceedings 22nd international symposium on mathematical foundations of computer science, MFCS’97 (pp. 29–36). · Zbl 0941.05057
[17] Borgne, L. (1994). Automatic frequency assignment for cellular networks using local search heuristics. Master’s thesis, Uppsala University.
[18] Borndörfer, R., Eisenblätter, A., Grötschel, M., & Martin, A. (1998a). Frequency assignment in cellular phone networks. Annals of Operations Research, 76, 73–93. · Zbl 0895.90090 · doi:10.1023/A:1018908907763
[19] Borndörfer, R., Eisenblätter, A., Grötschel, M., & Martin, A. (1998b). The orientation model for frequency assignment problems. Technical Report TR 98-01, Konrad-Zuse-Zentrum für Informationstechnik Berlin. · Zbl 0895.90090
[20] Bouju, A., Boyce, J. F., Dimitropoulos, C. H. D., Vom Scheidt, G., & Taylor, J. G. (1995a). Tabu search for the radio links frequency assignment problem. In Applied decision technologies (ADT’95), London.
[21] Bouju, A., Boyce, J. F., Dimitropoulos, C. H. D., Vom Scheidt, G., Taylor, J. G., Likas, A., Papageorgiou, G., & Stafylopatis, A. (1995b). Intellegent search for the radio links frequency assignment problem. In International conference for digital signal processing (DSP’95), Limassol, Cypres.
[22] Box, F. (1978). A heuristic technique for assigning frequencies to mobile radio nets. IEEE Transactions on Vehicular Technology, 27, 57–74. · doi:10.1109/T-VT.1978.23724
[23] Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22, 251–256. · Zbl 0394.05022 · doi:10.1145/359094.359101
[24] Cabon, B., De Givry, S., Lobjois, L., Schiex, T., & Warners, J. P. (1999). Benchmarks problems: Radio link frequency assignment. Constraints, 4, 79–89. · Zbl 1020.94500 · doi:10.1023/A:1009812409930
[25] Calamoneri, T. (Ed.). (2006). International Journal of Mobile Network Design and Innovation, 1, 2. · doi:10.1504/IJMNDI.2006.010811
[26] CALMA website. (1995). EUCLID CALMA project. Publications and instances available at FTP Site: ftp://ftp.win.tue.nl/pub/techreports/CALMA/ .
[27] Capone, A., & Trubian, M. (1999). Channel assignment problem in cellular systems: a new model and a tabu search algorithm. IEEE Transactions on Vehicular Technology, 48(4), 1252–1260. · doi:10.1109/25.775373
[28] Carlsson, M., & Grindal, M. (1993). Automatic frequency assignment for cellular telephones using constraint satisfaction techniques, In Proceedings of the tenth international conference on logic programming (pp. 648–665).
[29] Castelino, D. J., Hurley, S., & Stephens, N. M. (1996). A tabu search algorithm for frequency assignment. Annals of Operations Research, 63, 301–319. · Zbl 0851.90094 · doi:10.1007/BF02125459
[30] Chang, K.-N., & Kim, S. (1997). Channel allocation in cellular radio networks. Computers and Operations Research, 24(9), 849–860. · Zbl 0891.90166 · doi:10.1016/S0305-0548(96)00098-6
[31] Christofides, N. (1975). Graph theory: An algorithmic approach. London: Academic. · Zbl 0321.94011
[32] Colombo, G. (2006). A genetic algorithm for frequency assignment with problem decomposition. International Journal of Mobile Network Design and Innovation, 1(2), 102–112. · doi:10.1504/IJMNDI.2006.010812
[33] Cooper, M. C., de Givry, S., & Schiex, T. (2007). Optimal soft arc consistency, In Proceedings of international joint conference on artificial intelligence (IJCAI’2007), Hyderabad, India. · Zbl 1213.68580
[34] Correia, L. M. (Ed.). (2001). Wireless flexible personalized communications–COST 259: European co-operation in mobile radio research. New York: Wiley. COST Action 259–Final Report.
[35] Costa, D. (1993). On the use of some known methods for t-colourings of graphs. Annals of Operations Research, 41, 343–358. · Zbl 0771.68089 · doi:10.1007/BF02023000
[36] Cozzens, M. B., & Roberts, F. S. (1982). T-colorings of graphs and the channel assignment problem. Congressus Numerantium, 35, 191–208.
[37] Crisan, C., & Mühlenbein, H. (1998). The breeder genetic algorithm for frequency assignment. In Lecture notes in computer science (Vol. 1498, pp. 897–906).
[38] Crompton, W., Hurley, S., & Stephens, N. M. (1994). A parallel genetic algorithm for frequency assignment problems. In Proceedings IMACS/IEEE international symposium on signal processing, robotics and neural networks (pp. 81–84). Lille, France, April 1994.
[39] Cuppini, M. (1994). A genetic algorithm for channel assignment problems. European Transactions on Telecommunications and Related Technologies, 5, 285–294. · doi:10.1002/ett.4460050219
[40] Del Re, E., Fantacci, R., & Ronga, L. (1996). A synamic channel allocation technique based on Hopfield neural networks. IEEE Transactions on Vehicular Technology, 45, 26–32. · doi:10.1109/25.481817
[41] Dorne, R., & Hao, J.-K. (1995). An evolutionary approach for frequency assignment in cellular radio networks. In IEEE international conference on evolutionary computing, Perth, Australia.
[42] Dorne, R., & Hao, J.-K. (1996). Constraint handling in evolutionary search: A case study of the frequency assignment. In Lecture notes in computer science (Vol. 1141, pp. 801–810).
[43] Dorne, R., & Hao, J.-K. (1998). A new genetic local search algorithm for graph coloring. In Lecture notes in computer science (Vol. 1498, pp. 745–754).
[44] Dunkin, N., & Allen, S. M. (1997). Frequency assignment problems: Representations and solutions. Technical Report CSD-TR-97-14 Royal Holloway, University of London.
[45] Dunkin, N., Bater, J., Jeavons, P., & Cohen, D. (1998). Towards high order constraint representations for the frequency assignment problem. Technical Report CSD-TR-98-05, Royal Holloway University of London.
[46] Dupont, A., Alvernhe, E., & Vasquez, M. (2004). Efficient filtering and tabu search on a consistent neighbourhood for the frequency assignment problem with polarisation. Annals of Operations Research, 130, 179–198. · Zbl 1062.90010 · doi:10.1023/B:ANOR.0000032575.38969.ab
[47] Duque-Antón, M., Kunz, D., & Rüber, B. (1993). Channel assignment for cellular radio using simulated annealing. IEEE Transactions on Vehicular Technology, 42, 14–21. · doi:10.1109/25.192382
[48] Eisenblätter, A. (2001). Frequency assignment in GSM networks: Models, heuristics, and lower bounds. PhD thesis, Technische Universität Berlin, Berlin, Germany, 2001.
[49] Eisenblätter, A. (2002). The semidefinite relaxation of the k-partition polytope is strong. In W. J. Cook & A. S. Schulz (Eds.), Lecture notes in computer science: Vol. 2337. Proceedings of the 9th conference on integer programming and combinatorial optimization (IPCO’02) (pp. 273–290). Berlin: Springer. · Zbl 1049.90136
[50] Eisenblätter, A., Grötschel, M., & Koster, A. M. C. A. (2002). Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory, 22, 51–88. · Zbl 1055.05147
[51] Eisenblätter, A., Geerdes, H.-F., & Siomina, I. (2006). Integrated access point placement and channel assignment for wireless LANs in an indoor office environment. Technical Report 346 Matheon Berlin, Germany. URL http://www.matheon.de . To appear in Proceedings of IEEE WoWMoM, Helsinki, Finland, 2007.
[52] Erdos, P., Rubin, A. L., & Taylor, H. (1979). Choosability in graphs. Congressus Numerantium, 26, 125–157.
[53] FAP (2006). Frequency assignment problems, December 2006. URL http://www.fap.ema.fr/ .
[54] FAP web (2000–2007). A website devoted to frequency assignment. URL http://fap.zib.de . Maintained by A. Eisenblätter & A. M. C. A. Koster.
[55] Fischetti, M., Lepschy, C., Minerva, G., Romanin-Jacur, G., & Toto, E. (2000). Frequency assignment in mobile radio systems using branch-and-cut techniques. European Journal of Operational Research, 123, 241–255. Previously published as technical report of the Universita di Padova. · Zbl 0961.90051 · doi:10.1016/S0377-2217(99)00254-4
[56] Funabiki, N., & Takefuji, Y. (1992). A neural network parallel algorithm for channel assignment problems in cellular radio networks. IEEE Transactions on Vehicular Technology, 41, 430–437. · doi:10.1109/25.182594
[57] Galinier, P., & Hao, J.-K. (2004). A general approach for constraint solving by local search. Journal of Mathematical Modelling and Algorithms, 3, 73–88. · Zbl 1076.68071 · doi:10.1023/B:JMMA.0000026709.24659.da
[58] Galinier, P., Gendreau, M., Soriano, P., & Bisaillon, S. (2005). Solving the frequency assignment problem with polarization by local search and tabu. 4OR: A Quarterly Journal of Operations Research, 3, 59–78. · Zbl 1090.90120 · doi:10.1007/s10288-004-0056-4
[59] Gamst, A. (1986). Some lower bounds for a class of frequency assignment problems. IEEE Transactions on Vehicular Technology, 35, 8–14. · doi:10.1109/T-VT.1986.24063
[60] Gamst, A. (1991). Application of graph theoretical methods to GSM radio network planning. In Proceedings of IEEE international symposium on circuits and systems (Vol. 2, pp. 942–945).
[61] Gamst, A., & Rave, W. (1982). On frequency assignment in mobile automatic telephone systems. In Proceedings of GLOBECOM’82. New York: IEEE.
[62] Giortzis, A. I., & Turner, L. F. (1997). Application of mathematical programming to the fixed channel assignment problem in mobile radio networks. IEE Proceedings–Communications, 144, 257–264.
[63] Graham, J. S., Montemanni, R., Moon, J. N. J., & Smith, D. H. (2007, to appear). Frequency assignment, multiple interference and binary constraints, ACM Wireless Networks.
[64] Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68, 1497–1514. · doi:10.1109/PROC.1980.11899
[65] Hao, J.-K., & Dorne, R. (1996). Study of genetic search for the frequency assignment problem. In Lecture notes in computer science (Vol. 1063, pp. 333–344).
[66] Hao, J.-K., & Perrier, L. (1999). Tabu search for the frequency assignment problem in cellular radio networks. Technical Report LGI2P, EMA-EERIE, Parc Scientifique Georges Besse, Nimes, France.
[67] Hao, J.-K., Dorne, R., & Galinier, P. (1998). Tabu search for frequency assignment in mobile radio networks. Journal of Heuristics, 4, 47–62. · Zbl 1071.90578 · doi:10.1023/A:1009690321348
[68] Hellebrandt, M., & Heller, H. (2000). A new heuristic method for frequency assignment. Technical Report TD(00) 003 COST 259 Valencia, Spain, January 2000.
[69] Hertz, A., Schindl, D., & Zufferey, N. (2005). Lower bounding and tabu search procedures for the frequency assignment problem with polarization constraints. 4OR: A Quarterly Journal of Operations Research, 3, 139–161. · Zbl 1134.90471 · doi:10.1007/s10288-004-0057-3
[70] Hurley, S. (2002). Planning effective cellular mobile radio networks. IEEE Transactions on Vehicular Technology, 12(5), 243–253. · doi:10.1109/25.994802
[71] Hurley, S., & Smith, D. H. (2002). Meta-heuristics and channel assignment. In R. Leese & S. Hurley (Eds.), Methods and algorithms for radio channel assignment. Oxford: Oxford University Press, Chap. 3. · Zbl 1027.94500
[72] Hurley, S., Smith, D. H., & Thiel, S. U. (1997). FASoft: A system for discrete channel frequency assignment. Radio Science, 32, 1921–1939. · doi:10.1029/97RS01866
[73] Jaimes-Romero, F. J., Munoz-Rodriguez, D., & Tekinay, S. (1996). Channel assignment in cellular systems using genetic algorithms. In Proceedings of the 46th IEEE vehicular technology conference (pp. 741–745), Atlanta, USA.
[74] Janssen, J., & Kilakos, K. (1999). An optimal solution to the ”Philadelphia” channel assignment problem. IEEE Transactions on Vehicular Technology, 48(3), 1012–1014. Previously published as report CDAM-96-16 London School of Economics. · doi:10.1109/25.765037
[75] Janssen, J., & Wentzell, T. (2000). Lower bounds from tile covers for the channel assignment problem. Technical Report G-2000-09 GERAD, HEC, Montreal, Canada. · Zbl 1088.90034
[76] Jaumard, B., Marcotte, O., & Meyer, C. (1998). Estimation of the quality of cellular networks using column generation techniques. Technical Report G-98-02 Ecole Polytechnique de Montréal, January 1998.
[77] Jaumard, B., Marcotte, O., & Meyer, C. (1999). Mathematical models and exact methods for channel assignment in cellular networks. In B. Sansáo & P. Soriano (Eds.), Telecommunications network planning (pp. 239–255). Boston: Kluwer Academic, Chap. 13.
[78] Jaumard, B., Marcotte, O., Meyer, C., & Vovor, T. (2002). Comparison of column generation models for channel assignment in cellular networks. Discrete Applied Mathematics, 118, 299–322. Previously published as technical report of Ecole Polytechnique de Montréal, November 1998. · Zbl 0994.90099 · doi:10.1016/S0166-218X(02)00176-2
[79] Kalvenes, J., Kennington, J., & Olinick, E. (2005). Hierarchical cellular network design with channel allocation. European Journal of Operational Research, 160, 3–18. · Zbl 1067.90016 · doi:10.1016/j.ejor.2003.06.017
[80] Kapsalis, A., Chardaire, P., Rayward-Smith, V. J., & Smith, G. D. (1995). The radio link frequency assignment problem: A case study using genetic algorithms. In Lecture notes on computer science (Vol. 993, pp. 117–131).
[81] Karmarkar, N., Resende, M. G. C., & Ramakrishnan, K. G. (1991). An interior point algorithm to solve computationally difficult set covering problems. Mathematical Programming, 52, 597–618. · Zbl 0753.90046 · doi:10.1007/BF01582907
[82] Katzela, I., & Naghshineh, M. (1996). Channel assignment schemes for cellular mobile telecommunication systems. Personal Communications Magazine, 3(3), 10–31. · doi:10.1109/98.511762
[83] Kazantzakis, M. G., Demestichas, P. P., & Anagnostou, M. E. (1995). Optimum frequency reuse in mobile telephone systems. International Journal of Communications Systems, 8, 185–190. · doi:10.1002/dac.4500080304
[84] Kim, J.-S., Park, S., Dowd, P., & Nasrabadi, N. (1996). Cellular radio channel assignment using a modified Hopfield network. IEEE Transactions on Vehicular Technology, 46(4), 957–967.
[85] Knälmann, A., & Quellmalz, A. (1994). Solving the frequency assignment problem with simulated annealing. IEE Conference Publication, 396, 233–240.
[86] Kolen, A. W. J. (2007). A genetic algorithm for frequency assignment. Statistica Neerlandica, 61(1), 4–15. · Zbl 1122.90100 · doi:10.1111/j.1467-9574.2007.00357.x
[87] Kolen, A. W. J., van Hoesel, C. P. M., & van der Wal, R. (1994). A constraint satisfaction approach to the radio link frequency assignment problem. Technical Report 2.2.2 EUCLID CALMA project. · Zbl 0806.90028
[88] Koller, A. E., & Noble, S. D. (2004). Domination analysis of greedy heuristics for the frequency assignment problem. Discrete Mathematics, 275, 331–338. · Zbl 1077.90081 · doi:10.1016/j.disc.2003.05.008
[89] Koster, A. M. C. A. (1999). Frequency assignment–models and algorithms. PhD thesis, Maastricht University.
[90] Koster, A. M. C. A., van Hoesel, C. P. M., & Kolen, A. W. J. (1998). The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23(3–5), 89–97. · Zbl 0957.90095 · doi:10.1016/S0167-6377(98)00043-1
[91] Koster, A. M. C. A., van Hoesel, C. P. M., & Kolen, A. W. J. (2001). Lower bounds for minimum interference frequency assignment problems. Ricerca Operativa, 30(94–95), 101–116.
[92] Koster, A. M. C. A., van Hoesel, C. P. M., & Kolen, A. W. J. (2002). Solving partial constraint satisfaction problems with tree decomposition. Networks, 40(3), 170–180. · Zbl 1027.90072 · doi:10.1002/net.10046
[93] Král, D. (2005). An exact algorithm for the channel assignment problem. Discrete Applied Mathematics, 145, 326–331. · Zbl 1084.05069 · doi:10.1016/j.dam.2004.01.020
[94] Kunz, D. (1991). Channel assignment for cellular radio using neural networks. IEEE Transactions on Vehicular Technology, 40, 188–193. · doi:10.1109/25.69987
[95] Lai, W. K., & Coghill, G. G. (1996). Channel assignment through evolutionary optimization. IEEE Transactions on Vehicular Technology, 45, 91–95. · doi:10.1109/25.481825
[96] Lee, Y., Kim, K., & Choi, Y. (2002). Optimization of AP placement and channel assignment in wireless LANs. In Proceedings of LCN’02, Tampa, FL.
[97] Leese, R., & Hurley, S. (Eds.) (2002). Methods and algorithms for radio channel assignment. Oxford lecture series in mathematics and its applications. Oxford: Oxford University Press. · Zbl 1027.94500
[98] Leung, K. K., & Kim, B.-J. (2003). Frequency assignment for IEEE 802.11 wireless networks. In Proceedings of VTC 2003-Fall, Orlando, FL.
[99] Ling, X., & Yeung, K. L. (2005). Joint access point placement and channel assignment for 802.11 wireless LANs. In Proceedings of WCNC 2005, New Orleans, LA.
[100] Maniezzo, V., & Carbonaro, A. (2000). An ants heuristic for the frequency assignment problem. Future Generation Computer Systems, 16, 927–935. · doi:10.1016/S0167-739X(00)00046-7
[101] Maniezzo, V., & Montemanni, R. (2000). An exact algorithm for the min-interference frequency assignment problem. Technical Report WP-CO0003 Scienze dell’Informazione, University of Bologna, Cesena, Italy.
[102] Mannino, C., & Sassano, A. (2003). An enumerative algorithm for the frequency assignment problem. Discrete Applied Mathematics, 129(1), 155–169. · Zbl 1023.68004 · doi:10.1016/S0166-218X(02)00239-1
[103] Mannino, C., Oriolo, G., & Sassano, A. (2000). Weighted stable set problem in k-thin graphs. Technical Report 09–00 Universitá di Roma ”La Sapienza”.
[104] Mathar, R., & Mattfeldt, J. (1993). Channel assignment in cellular radio networks. IEEE Transactions on Vehicular Technology, 42, 647–656. · doi:10.1109/25.260746
[105] Mathar, R., & Schmeink, M. (2001). Optimal base station positioning and channel assignment for 3G mobile networks by integer programming. Annals of Operations Research, 107, 225–236. · Zbl 1015.90012 · doi:10.1023/A:1014959317542
[106] Mehrotra, A., & Trick, M. A. (1996). A column generation approach for graph coloring. INFORMS Journal on Computing, 8, 344–354. · Zbl 0884.90144 · doi:10.1287/ijoc.8.4.344
[107] Metzger, B. H. (1970). Spectrum management technique. Presentation at 38th National ORSA meeting, Detroit, MI.
[108] Mishra, A., Banerjee, S., & Arbaugh, W. (2005). Weighted coloring based channel assignment for wlans. ACM SIGMOBILE Mobile Computing and Communications Review, 9(3), 19–31. · Zbl 05443636 · doi:10.1145/1094549.1094554
[109] Montemanni, R., Smith, D. H., & Allen, S. M. (2002a). Lower bounds for fixed spectrum frequency assignment. Annals of Operations Research, 107(1–4), 237–250. · Zbl 1015.90069 · doi:10.1023/A:1014911401612
[110] Montemanni, R., Smith, D. H., & Allen, S. M. (2002b). An ANTS algorithm for the minimum-span frequency-assignment problem with multiple interference. IEEE Transactions on Vehicular Technology, 15(5), 949–953. · doi:10.1109/TVT.2002.800634
[111] Montemanni, R., Moon, J. N. J., & Smith, D. H. (2003). An improved tabu search algorithm for the fixed spectrum frequency assignment problem. IEEE Transactions on Vehicular Technology, 52(4), 891–901. · doi:10.1109/TVT.2003.810976
[112] Montemanni, R., Smith, D. H., & Allen, S. M. (2004). An improved algorithm to determine lower bounds for the fixed spectrum frequency assignment problem. European Journal of Operational Research, 156, 736–751. · Zbl 1107.90389 · doi:10.1016/S0377-2217(03)00127-9
[113] Moon, J. N. J., Hughes, L. A., & Smith, D. H. (2005). Assignment of frequency lists in frequency hopping networks. IEEE Transactions on Vehicular Technology, 54(3), 1147–1159. · doi:10.1109/TVT.2005.844659
[114] Murphey, R. A., Pardalos, P. M., & Resende, M. G. C. (1999). Frequency assignment problems. In D.-Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization, Supplement Volume A. Dordrecht: Kluwer Academic. · Zbl 1253.90137
[115] Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley. · Zbl 0652.90067
[116] Ngo, C. Y., & Li, V. O. K. (1998). Fixed channel assignment in cellular radio networks using a modified genetic algorithm. IEEE Transactions on Vehicular Technology, 47, 163–171. · doi:10.1109/25.661043
[117] Nielsen, T., & Wigard, J. (2000). Performance enhancements in a frequency hopping GSM network. Dordrecht: Kluwer Academic. ISBN: 0 7923 7819 9.
[118] Padberg, M. (1989). The boolean quadric polytope: Some characteristics, facets and relatives. Mathematical Programming, 45, 139–172. · Zbl 0675.90056 · doi:10.1007/BF01589101
[119] Palpant, M., Artigues, C., & Michelon, P. (2002). A heuristic for solving the frequency assignment problem. In XI Latin–Iberian–American congress of operations research (CLAIO 2002). · Zbl 1066.90037
[120] Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity. New Jersey: Prentice-Hall. · Zbl 0503.90060
[121] Park, T., & Lee, C. Y. (1996). Application of the graph coloring algorithm to the frequency assignment problem. Journal of the Operations Research Society of Japan, 39, 258–265. · Zbl 0863.90131
[122] Petford, A., & Welsh, D. (1989). A randomised 3-colouring algorithm. Discrete Mathematics, 74, 253–261. · Zbl 0667.05025 · doi:10.1016/0012-365X(89)90214-8
[123] Quellmalz, A., Knälmann, A., & Müller, B. (1995). Efficient frequency assignment with simulated annealing. IEE Conference Publication, 407(2), 301–304.
[124] Raychaudhuri, A. (1994). Further results on t-coloring and frequency assignment problems. SIAM Journal on Discrete Mathematics, 7(4), 605–613. · Zbl 0810.05026 · doi:10.1137/S0895480189171746
[125] Riihijärvi, J., Petrova, M., & Mähönen, P. (2005). Frequency allocation for WLANs using graph colouring techniques. In Proceedings of WONS’05, St. Moritz, Switzerland.
[126] ROADEF website. (2001). ROADEF Challenge. URL http://www.prism.uvsq.fr/\(\sim\)vdc/ROADEF/CHALLENGES/2001/challenge(2001)html .
[127] Roberts, F. S. (1991). t-colorings of graphs: Recent results and open problems. Discrete Mathematics, 93, 229–245. · Zbl 0751.05042 · doi:10.1016/0012-365X(91)90258-4
[128] Rouskas, A. N., Kazantzakis, M. G., & Anagnostou, M. E. (1995). Optimal channel assignment in cellular networks. International Journal of Communication Systems, 8, 359–364. · doi:10.1002/dac.4500080603
[129] Rushforth, C. K., & Wang, W. (1997). Local search for channel assignment in cellular mobile networks. In DIMACS series in discrete mathematics and theoretical computer science (Vol. 35, pp. 689–709). Providence: American Mathematical Society. · Zbl 0891.68030
[130] Sandalidis, H. G., Stavroulakis, P. P., & Rodriguez-Tellez, J. (1999). Borrowing channel assignment strategies based on heuristic techniques for cellular systems. IEEE Transactions on Neural Networks, 10, 176–181. · doi:10.1109/72.737504
[131] Schiex, T., de Givry, S., & Sanchez, M. (2006). Toulbar2–an open source weighted constraint satisfaction solver. URL http://mulcyber.toulouse.inra.fr/projects/toulbar2/ .
[132] Sivarajan, K. N., McEliece, R. J., & Ketchum, J. W. (1989). Channel assignment in cellular radio. In Proceedings of the 39th IEEE vehicular technology conference (pp. 846–850).
[133] Smith, D. H., Hurley, S., & Thiel, S. U. (1998). Improving heuristics for the frequency assignment problem. European Journal of Operational Research, 107, 76–86. · Zbl 0943.90056 · doi:10.1016/S0377-2217(98)80006-4
[134] Smith, D. H., Taplin, R. K., & Hurley, S. (2001). Frequency assignment with complex co-site constraints. IEEE Transaction on Electromagnetic Compatibility, 43(2), 210–218. · doi:10.1109/15.925542
[135] Smith, D. H., Allen, S. M., & Hurley, S. (2002). Characteristics of good meta-heuristic algorithms for the frequency assignment problem. Annals of Operations Research, 107(1–4), 285–301. · Zbl 1015.90050 · doi:10.1023/A:1014919603430
[136] Smith, D. H., Hughes, L. A., Moon, J. N. J., & Montemanni, R. (2007). Measuring the effectiveness of frequency assignment algorithms. IEEE Transactions on Vehicular Technology, 56, 331–341. · doi:10.1109/TVT.2006.883770
[137] Smith, K. A., & Palaniswami, M. (1997). Static and dynamic channel assignment using neural networks. IEEE Journal on Selected Areas in Communications, 15, 238–249. · doi:10.1109/49.552073
[138] Sung, C. W., & Wong, W. S. (1997). Sequential packing algorithm for channel assignment under cochannel and adjacent channel interference constraint. IEEE Transactions on Vehicular Technology, 46, 676–685. · doi:10.1109/25.618193
[139] Tcha, D., Chung, Y., & Choi, T. (1997). A new lower bound for the frequency assignment problem. IEEE/ACM Transactions on Networking, 5, 34–39. · doi:10.1109/90.554720
[140] Thuve, H. (1981). Frequency planning as a set partitioning problem. European Journal of Operational Research, 6, 29–37. · doi:10.1016/0377-2217(81)90325-8
[141] Tiourine, S. R., Hurkens, C. A. J., & Lenstra, J. K. (1995). An overview of algorithmic approaches to frequency assignment problems. In Calma symposium on combinatorial algorithms for military applications (pp. 53–62).
[142] Tsang, E., & Voudouris, C. (1998). Solving the radio link frequency assignment problem using guided local search. In NATO symposium on radio length frequency assignment, Aalborg, Denmark, 1998. http://cswww.essex.ac.uk/CSP/papers.html .
[143] Valenzuela, C., Hurley, S., & Smith, D. H. (1998). A permutation based genetic algorithm for minimum span frequency assignment. In Lecture notes in computer science (Vol. 1498, pp. 907–916).
[144] van Benthem, H. P. (1995). GRAPH generating radio link frequency assignment problems heuristically. Master’s thesis, Delft University of Technology.
[145] Verfaillie, G., Lemaître, M., & Schiex, T. (1996). Russian doll search for solving constraint optimization problems. In Proceedings of the 13th international conference on artificial intelligence (AAAI-96) (pp. 181–187), Portland, OR, USA.
[146] Villegas, E. G., Ferré, R. V., & Aspas, J. P. (2005). Implementation of a distributed dynamic channel assignment mechanism for IEEE 802.11 networks. In Proceedings of PIMRC 2005, September 2005.
[147] Vizing, V. G. (1965). Critical graphs with given chromatic class. Diskretniyi Analiz, 5, 9–17 (in Russian).
[148] Walser, J. P. (1996). Feasible cellular frequency assignment using constraint programming abstractions. In Proceedings of the workshop on constraint programming applications (CP96), Cambridge, MA, USA.
[149] Wang, L., & Gu, W. (2004). Genetic algorithms with stochastic ranking for optimal channel assignment in mobile communications. In Lecture notes in computer science (Vol. 3314, pp. 154–159).
[150] Wang, W., & Rushforth, C. K. (1996). An adaptive local-search algorithm for the channel-assignment problem (CAP). IEEE Transactions on Vehicular Technology, 45, 459–466. · doi:10.1109/25.533761
[151] Warners, J. P., Terlaky, T., Roos, C., & Jansen, B. (1997). A potential reduction approach to the frequency assignment problem. Discrete Applied Mathematics, 78, 251–282. · Zbl 0893.90132 · doi:10.1016/S0166-218X(96)00139-4
[152] Yuan, D., Björklund, P., & Värbrand, P. (2002). Optimal frequency planning in mobile networks with frequency hopping. Technical Report LiTH-ITN-R-2002–3 Linköping University, Norrköping, Sweden submitted to Computers and Operations Research.
[153] Zerovnik, J. (1997). Experiments with a randomized algorithm for a frequency assignment problem. Technical Report 97–27, Ecole Normale Supérieure de Lyon.
[154] Zhang, M., & Yum, T. P. (1991). The nonuniform compact pattern allocation algorithm for cellular mobile systems. IEEE Transactions on Vehicular Technology, 40, 387–391. · doi:10.1109/25.289419
[155] Zoellner, J. A., & Beall, C. L. (1977). A breakthrough in spectrum conserving frequency assignment technology. IEEE Transactions on Electromagnetic Compatibility, 19, 313–319. · doi:10.1109/TEMC.1977.303601
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.