Besides presenting key results in this area, I will attempt to 
give a feel for its important open problems.
Pre-requisites are: a graduate level algorithms course, and some
understanding of LP-duality theory. The course is based on the book 
I am writing on this topic, a preliminary version of which can be 
obtained from my home page: http://www.cc.gatech.edu/fac/Vijay.Vazirani.

Here is a tentative list of topics:

1). Combinatorial algorithms: Steiner trees, TSP, multiway cut and cut, 
feedback vertex set, facility location problems, K-connected subgraph.

2). Primal-dual schema based algorithms: set cover, metric Steiner
forest, multicut and integer multicommodity flow in trees.

3). Multicommodity flows: multicut, sparsest cut, low distortion
l1-embeddability of metrics.

4). Semidefinite programming: max cut.

5). Estimating network reliability.

6). PTAS for scheduling and Euclidean TSP, FPAS for knapsack.

7). Hardness of approximability.

This course is part of the DIMACS Special Year on Large Scale Discrete Optimization.



 Back to Large Scale Discrete Optimization index