Dingzhu Du Boeken

Focusing on the intersection of operations research, computer science, and applied mathematics, this book delves into combinatorial optimization, highlighting its significance in diverse applications such as network design, scheduling, and computational biology. It traces the historical roots of the field to linear programming, noting key advancements like the ellipsoid method and interior point approaches that have revolutionized problem-solving. The text emphasizes the commonality of discrete problems and their connection to linear programming, including the development of approximation algorithms for NP-hard issues.

The textbook uniquely categorizes approximation algorithms by their design techniques, enabling readers to explore similar algorithms in a cohesive manner. This structured approach differentiates it from other theoretical computer science resources, facilitating a deeper understanding of the algorithms' underlying principles and applications.

Combinatorial optimization is a dynamic field at the intersection of operations research, computer science, and applied mathematics, with applications ranging from network design to machine vision and scheduling. It encompasses diverse areas like linear and integer programming, graph theory, and artificial intelligence. The discipline evolved from linear programming, which has significant applications in resource allocation and planning. Key developments, such as the ellipsoid method and interior point approaches, have introduced polynomial-time algorithms that greatly influence combinatorial optimization solutions.

This book serves as a textbook for graduate students in theoretical computer science and a reference for researchers on approximation algorithms. Unlike existing problem-oriented texts, it offers a structured, technique-oriented approach, organizing algorithms by design techniques to enhance understanding and teaching of the subject.

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have important applications in communication networks, especially in wireless networks, as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.