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 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 than 200 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.