Scope and Purpose: It is a fundamental course in combinatorial
optimization. I realized that the graduate students in this area pay
attention to concrete problems without considering the mathematics behind.
It is due to the current course system. In this course I first introduce
Primal Dual method for linear programming. With this method we can solve
several classical network problems, such as Shortest Path, Max Flow and Min-Cost
Flow. The most interesting point is that the solution method helps us explore
some combinatorial algorithms.
Winter Semester, 2004-2005
Design
and Analysis of Algorithms (in English)
Audience: Ph.D. students
Scope and Purpose: It is an advanced course in combinatorial optimization.
To solve a problem we need algorithms. General speaking the cost of an
algorithm is in conflict with the quality of the solution given by the
algorithm. The cost usually appears as running time, space occupied as well
as information cost, while the quality of the solution is the error bound
on the optimum. Along this line there can be many algorithms, like exact
algorithms (the best quality of solution but the cost incurred might be
huge), approximation algorithms (good quality and small cost), metaheuristics
(possibly good quality and small cost), on-line algorithms (quality depending
on problem itself and small cost). This course consists of approximation
algorithms for hard problems and on-line algorithms for several important
problems arising in computer science. In particular we show a number of techniques
in design and analysis of algorithms, such as designing PTAS, L-Reduction,
potential function method etc.
Spring-Summer Semester, 2004-2005
Analysis
II (in Chinese)
Audience: Undergraduate students of math department