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：
[1] Papadimitriou C.H. &Steiglitz.K., Combinatorial Optimization: Algorithms and Complexity. Printice—Hall Inc, 1982.
[2] Ausiello G. et al Complexity and Approximation Springer , 1999.
Author：Tiande Guo (School of Mathematical Sciences, GUCAS)
Date：June, 2010
