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:






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

Polar Duality Polar Dual 2

4:Oct 11


Neva pdf

5:Oct 15

Facility Location

Ioannis pdf

Facility Location Paper

6:Oct 18

Min Cost Steiner Forest

Ethan pdf

7:Oct 22

Prize Collecting Steiner Forest

Neva pdf

Prize Collecting Steiner

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

Kamal's Multicast Paper

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