Introduction to Combinatorial Optimization

Introductory courses in combinatorial optimization are popular at the upper undergraduate/graduate levels in computer science, industrial engineering, and business management/OR, owed to its wide applications in these fields. There are several published textbooks that treat this course and the authors have used many of them in their own teaching experiences. This present text fills a gap and is organized with a stress on methodology and relevant content, providing a step-by-step approach for the student to become proficient in solving combinatorial optimization problems. Applications and problems are considered via recent technology developments including wireless communication, cloud computing, social networks, and machine learning, to name several, and the reader is led to the frontiers of combinatorial optimization. Each chapter presents common problems, such as minimum spanning tree, shortest path, maximum matching, network flow, set-cover, as well as key algorithms, suchas greedy algorithm, dynamic programming, augmenting path, and divide-and-conquer. Historical notes, ample exercises in every chapter, strategically placed graphics, and an extensive bibliography are amongst the gems of this textbook.

Discussion of common applications enables the student to reach the forefront of research Gives the reader a global and comprehensive view on how to solve combinatorial optimization problems Emphasizes methodology and design techniques

Auteur

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 University, UK. He is also the recipient of UF 2009 International Educator Award; Medal (in recognition of broad contributions in science and engineering) of the University of Catani, Italy; EURO Gold Medal (EGM); Honorary Doctor of Science Degree, Wilfrid Laurier University, Canada; Senior Fulbright Specialist Award; University of Florida Research Foundation Professorship; and IBM Achievement Award.

Xiaodong Hu is a research professor at the Institute of Applied Mathematics, Chinese Academy of Sciences. He was the president of OR society of China a few year ago. His research interests include combinatorial optimization, and approximation algorithms, to name just two.

Weili Wu is pra ofessor of computer science at the University of Texas at Dallas. Her research interests include optimization theory, big data management and analysis, social networks, database systems, and wireless sensor networks, to name just several. She has published more than200 journal papers and 100 conference papers. Especially, she made several influential contributions in the study of wireless sensor networks, which are accumulated in a Springer publication "Optimal Coverage in Wireless Sensor Networks".

Résumé

"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)

Contenu

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.