Review of the Book “Optimization in Computer Engineering—Theory and Applications”: Chapter 8—Applying Graph Coloring to Frequency Assignment

Abstract

This book focuses on the relationship between theory and applications of various optimization problems in computer engineering. In the first half of the book the theoretical foundations are presented, such as some selected graph algorithms, integer linear programming and complexity theory. The second half of the book brings the theory closer to the reader by applying them to real-world optimization problems. Its aim is to bridge the often significant gap between theory and applications bringing additional value to both: the theory becomes more interesting in light of a possible application and understanding the hardness and possible solutions of the real-world problem definitely benefits from a strong theoretical background. Chapter 8 is a good example of the above. Here the authors present several versions of the frequency assignment problem (FAP), which is an important practical optimization problem arising in wireless network design. It is shown how FAP can be reduced to the earlier presented graph coloring problem. It is interesting to note that often the practical problem needs significant simplification in order to fit into the model that the theory is able to handle, or the theoretical problem needs to be extended to be able to model the needs of the practical application. Various generalizations of the simple graph coloring problem such as list coloring and T-coloring are introduced to model the constraints of the FAP. With this reduction the specific engineering problem can be han-dled through well-understood mathematical models. Besides showing the reduction to the graph coloring problem, the authors apply a graph coloring solver on industry benchmark FAP instances to further understand the characteristics of the real-world FAP. They show that there are significant differences in the difficulty of the problem on random and real-world graphs and that the parameters of the particular instance play a crucial role in the hardness of the problem. They show that the FAPs show a phase transition property in every input parameter, ie. there is a critical parameter combination where the problem gets extremely hard, but otherwise the problem can be solved relatively easily even on large real-world networks. Readers will surely benefit from the unique nature of the book that brings theory and applications close together in a well-understandable yet theoretically solid way.