CS 522: Combinatorial Optimizationtaes
Fall '04
Kamal Jain
Description: This course will focus on various techniques from Combinatorial Optimization used in Computer Science. Possible topics will include Linear Programming Duality, Graph Theory (Flow and Cuts), Ellipsoid Algorithm, Submodular Functions, Matroid Theory, and Lattices. The focus of the course will be to develop the intuition and not the intimidating technical details. The instructor will take many examples from Computer Science (naturally some of them from his own work) to describe the concepts.
Lecturer: Kamal Jain kjain@cc.gatech.edu
CSE 403
MF 1:30-2:50
Links to previous Courses:
http://www.cc.gatech.edu/classes/AY2000/cs1050_fall/ http://www.cc.gatech.edu/classes/cs3156b_99_winter/
|
Lecture |
Topics |
Notes |
References |
|---|---|---|---|
|
1:Oct 1 |
Introduction to Combinatorial Optimization |
Atri pdf |
|
|
2:Oct 4 |
Convex Sets, Polyhedra, Separation Theorem |
Chris pdf |
|
|
3:Oct 8 |
Polar Duality and Farkas' Lemma |
Daniel pdf |
|
|
4:Oct 11 |
Duality |
Neva pdf |
|
|
5:Oct 15 |
Facility Location |
Ioannis pdf |
|
|
6:Oct 18 |
Min Cost Steiner Forest |
Ethan pdf |
|
|
7:Oct 22 |
Prize Collecting Steiner Forest |
Neva pdf |
|
|
8:Oct 25 |
|
|
|
|
9:Oct 29 |
Prize Collecting Steiner (cont'd) |
Ning pdf |
|
|
10:Nov 1 |
Dynamic Programming Approximation (Knapsack, TSP) |
Tobias pdf |
|
|
11: Nov 5 |
Euclidean TSP, Tree decompositions |
Ioannis pdf |
|
|
12: Nov 8 |
Minor Graph Theory, Ellipsoid Algorithm |
Atri pdf |
|
|
13: Nov 12 |
Solving LPs with the Ellipsoid Algorithm |
Chris pdf |
Korte and Vygen on Combinatorial Optimization |
|
14: Nov 15 |
Minimizing Sub-modular functions |
Ning pdf |
|
|
15: Nov 19 |
Minimizing Sub-modular functions (cont'd) Edmund's theorem |
Neva pdf |
|
|
16: Nov 22 |
Sub-modular functions, network coding |
Atri pdf |
|
|
17: Nov 29 |
Network coding(cont'd), Lattices |
Daniel pdf |
|
|
18: Dec 3 |
Lattices and the Shortest Vector Problem |
Chris pdf |
|
|
19: Dec 6 |
The Lenstra, Lenstra and Lovasz Algorithm |
Ethan pdf |
|
|
20: Dec 10 |
Finding a point in a convex set if there is one with small description |
Ning pdf |
|