Fall 98 Selected Topics in OR

Approximation Algorithms

Vijay V. Vazirani
College of Computing
Georgia Institute of Technology

*Please Note: the first two class meetings will be held in the DIMACS Lounge, CoRE Building, Room 401

Course number: 16:711:613
Index number : 12995
Time: : T,Th 6th period- 4:30-5:50
RUTCOR Room 139
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