Combinatorial Optimization

  • 申立勇
  • Created: 2014-12-08
Combinatorial Optimization


Course No.S070105ZJ004

Course CategoryProfessional Basic Course


PrerequisitesLinear 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.


[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.

AuthorTiande Guo (School of Mathematical Sciences, GUCAS)

DateJune, 2010