Topics in Algorithms
CSC 5160
CSC 5160: Combinatorial Optimization and Approximation Algorithms
This is an introductory graduate course on algorithm design.
The aim is to provide a solid algorithmic background for researchers in computer science, engineering, or mathematics.
| Lecture: | Thursday 12:30-2:15 (ERB 803, ERB 703), Friday 9:30-11:15 (ERB 703) |
|---|---|
| Instructor: | Lap Chi Lau |
| Tutor: | Jerry J.L. Le |
| Link: | CSC 5160 (2007) |
There are two major topics in this course - combinatorial optimization and approximation algorithms. In each topic we'll study the basic results and techniques. The purpose is to have a broad view on different algorithmic techniques. An important method we'll focus on is linear programming, which is very useful in designing both exact algorithms and approximation algorithms.
- Combinatorial Optimization - Classical polynomial time solvable problems in combinatorial optimization, which have many applications in different areas. The algorithmic techniques developed to solving them are the basic elements in algorithm design.
- Bipartite matchings, general matchings, Hungarian method.
- Maximum flows, minimum cuts.
- Submodular functions, submodular flows, graph orientations.
- Linear and Integer Programming - A general and powerful tool for algorithm design. Many optimization problems can be modelled as linear programs, which can be solved in polynomial time. Sometimes surprisingly this gives us polynomial time algorithms to solve the problems exactly.
- Basic solutions, The simplex method, the ellipsoid method, separation oracle.
- The stable matching polytope, the matching polytope, path and flow polyhedra, iterative rounding, totally dual integrality (TDI).
- The duality theorem and its applications, primal-dual algorithms.
- Approximation Algorithms - An approach to cope with NP-hard problems. We'll study many different techniques to design approximation algorithms, such as combinatorial techniques, greedy methods, dynamic programming, linear programming and semidefinite programming.
- Combinatorial algorithms, minimum Steiner tree, the travelling salesman problem (TSP).
- Dynamic programming, the knapsack problem, approximation schemes (PTAS).
- Set cover, greedy algorithm, primal-dual algorithm, randomized rounding, scheduling, general assignment.
- Linear and Semidefinite Programming - Many best known approximation algorithms are based on linear programming and its generalization semidefinite programming. We'll study different techniques to obtain good approximation solutions from this general method, such as primal-dual schema, iterative relaxation and randomized rounding.
- Primal dual, online primal dual, ski rental.
- Iterative relaxation, network design.
- Semidefinite programming (SDP), maximum cut, graph colouring.
- Perfect graphs, Lovász theta function.
References: This course does not have a textbook. The following is a list of references.
 |
Alexander Schrijver Combinatorial Optimization: Polyhedra and Efficiency Springer, 2003 |
|---|---|
 |
Christos H. Papadimitriou, Kenneth Steiglitz Combinatorial Optimization: Algorithms and Complexity Dover Publications, 1998 |
 |
Alexander Schrijver Theory of Linear and Integer Programming John Wiley & Sons, 1998 |
 |
Vijay V. Vazirani Approximation Algorithms Springer, 2004 |