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:302: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 Submodular functions 
Ning pdf 

15: Nov 19 
Minimizing Submodular functions (cont'd) Edmund's theorem 
Neva pdf 

16: Nov 22 
Submodular 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 
