Introduction to Combinatorial Optimization

1. Introduction.-2. Divide-and-Conquer.- 3. Dynamic Programming and Shortest Path.- 4. Greedy Algorithm and Spanning Tree.- 5. Incremental Method and Maximum Network Flow.- 6. Linear Programming.- 7. Primal-Dual Methods and Minimum Cost Flow.- 8. NP-hard Problems and Approximation Algorithms.- 9. Restriction and Steiner Tree.- 10. Greedy Approximation and Submodular Optimization.- 11. Relaxation and Rounding. 12. Nonsubmodular Optimization.- Bibliography.

Ding-Zhu Du is Professor of Computer Science at the University of Texas at Dallas. For a number of years he was the Editor-in-Chief of the Journal of Combinatorial Optimization and the  combinatorial optimization series editor for the SOIA book series. Professor Du is co-editor of the first and second editions of the Handbook of Combinatorial Optimization. He was also co-author (with Pardalos and Wu) of the Kluwer publication "Mathematical Theory of Optimization."  

Panos M. Pardalos is Distinguished Professor Emeritus of Industrial and Systems Engineering at the University of Florida. Additionally, he is the Paul and Heidi Brown Preeminent Professor in Industrial & Systems Engineering. He is also an affiliated faculty member of the Computer and Information Science Department, the Hellenic Studies Center, and the Biomedical Engineering Program. He is also the Director of the Center for Applied Optimization. Dr. Pardalos is a world leading expert in global and combinatorial optimization. His recent research interests include network design problems, optimization in telecommunications, e-commerce, data mining, biomedical applications, and massive computing. He has co-authored and co-edited more than 30 books, as well as publishing more than 600 journal articles and conference proceedings. Prof. Pardalos is a Fellow of AAAS (American Association for the Advancement of Science), Fellow of American Institute for Medical and Biological Engineering (AIMBE), and EUROPT. He is a Distinguished International Professor by the Chinese Minister of Education; Honorary Professor of Anhui University of Sciences and Technology, China; Elizabeth Wood Dunlevie Honors Term Professor; Honorary Doctor, V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine; Foreign Associate Member of Reial Academia de Doctors, Spain; and Advisory board member of the Centre for Optimisation and Its Applications, Cardiff

"This book introduces combinatorial optimization with a methodology-oriented organization. It targets undergraduate and graduate students and contains a good mix of theoretical results (with proof) and examples, which helps the reader acquire ideas and concepts. The chapters end with a list of exercises for the students." (Francisco Chicano, Mathematical Reviews, January, 2024)
"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. ... this book is an excellent contribution to the field of combinatorial optimization, and it is highly recommended to the students and researchers in optimization." (Samir Kumar Neogy, zbMATH 1512.90001, 2023)