Combinatorial Optimization

• 申立勇
• Created: 2014-12-08
 Combinatorial Optimization Course No.：S070105ZJ004 Course Category：Professional Basic Course Period/Credits：40/2 Prerequisites：Linear Algebra, Linear Programming, Basic Probability. Aims & Requirements： This course is intended for graduate students of control theory and operational research, while can also serve as an elective for students from areas like management sciences, computer sciences, and other mathematical sciences. Through the study of this course, students are expected to not only acquaint basic technologies, but also understand the trends of development of combinatorial optimization, thus lay foundation for further research. Primary Coverage： Chapter 1 Introduction What’s Combinatorial Optimization? ; Relation with Other Disciplines. Chapter 2 Preparation Graph Theory and Network Optimization; Relations between Several Programming; Optimization Problems; Neighbors. Chapter 3 Algorithms and Complexity Two Classical Problems; Concept of Computational Complexity; Algorithms; Polynomial Time and Exponential Time. Chapter 4 LP and its Dual – Prime-Dual Algorithm History; Geometrical Explanation; Main Theorems; Simplex; Duality. Chapter 5 Prime-Dual Algorithms for Combinatorial Optimization Prime-Dual Algorithms for Shortest Path; for Maximum Flow; for Minimum Flow; for Hitchcock. Chapter 6 Efficient Algorithms for Combinatorial Optimization Problems Discussion of Complexity; for Maximum Flow; for Matching; for Weighted Matching. Chapter 7 “Hard” Combinatorial Optimization Problems Integer Programming; Convex Polyhedron; Uni-modular. Chapter 8 Matroid Minimum Spanning Tree and Greedy Algorithms; Basic Concepts of Matroid; Matroid and Combinatorial Optimization Problems. Chapter 9 NP and NP-Completeness NP Problems; NP-Completeness Problems; Polynomial Reduction; Cook Theorem; Six Foundational NPC Problems. Chapter 10 Approximation Algorithms Greedy Algorithms; PTAS and FPTAS; Stochastic Algorithms; Local Search; Heuristics. References：  Papadimitriou C.H. &Steiglitz.K., Combinatorial Optimization: Algorithms and Complexity. Printice—Hall Inc, 1982.  Ausiello G. et al Complexity and Approximation Springer , 1999. Author：Tiande Guo (School of Mathematical Sciences, GUCAS) Date：June, 2010