Introduction to combinatorial optimization (Q2160145)

The combinatorial optimization is a proper subfield of discrete optimization. In view of methodologies, combinatorial optimization and discrete optimization have very close relationship. In recent developments of technology, combinatorial optimization offers a lot of new applications and new research directions. In this book, the authors put together three components, the classic part of combinatorial optimization, approximation theory developed in recent years, and newly appeared nonlinear combinatorial optimization. The goal of the book is to provide the readers about the design and analysis of computer algorithm for exact optimal solution, design and analysis of approximation algorithms, and nonlinear combinatorial optimization. The various chapters of the book may be read independently, what may be a benefit for some readers. The book is organized in 12 chapters and consists of three building blocks. The first block contains Chapters 2--7, which can be divided into two parts. The first part is on algorithms with self-reducibility, including the divide-and-conquer, the dynamic program, the greedy algorithm, the local search, the local ratio, etc., which are organized into Chapters 2--4. The second part is on incremental method, including the primal algorithm, the dual algorithm, and the primal-dual algorithm, which are organized also into Chapters 5--7. The second block contains Chapters 8--11, covering the fundamental knowledge on computational complexity, including theory on NP-hardness and inapproximability, and basic techniques for design of approximation, including the restriction, the greedy approximation, and the relaxation with rounding. The third block contains Chapters 10, 11, and 12. Since Chapters 10--11 serve both the second and the third blocks, selected examples are mainly coming from the submodular optimization. Currently nonsubmodular optimization is an active research area. There are lots of recent publications reported in the literature on this topic. Chapter 12 is devoted to the nonsubmodular optimization and it can be seen as an introduction to this area. Researchers and practitioners in industrial engineering, management science, economics, computer science, and environmental science will find this book valuable in their research and study. Because of its emphasis on practical applications, the book can appropriately be used as a textbook in a graduate course. All the algorithms are clearly explained and presented. It is a very valuable book for successful application of real problems from combinatorial optimization. Overall, this book is an excellent contribution to the field of combinatorial optimization, and it is highly recommended to the students and researchers in optimization.