Course: Exact and Approximation algorithms
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.

Office hours: By appointment


Subjects covered:
Linear programming
A sketch of the Ellipsoids algorithm
Strong duality and correctness of the Kruskal Algorithm
Exact algorithm for the Assignment Problem.
Exact algorithm for matching and Vertex cover on Bipartite graph
Basic approximation algorithms
Dual fitting and primal dual for Set Cover
The submodular Cover and connected Polymatroid problems
Approximating facility location via filtering
Expectation of Random Variables
Randomized approximation algorithms.
Local search for approximation.
Scheduling unrelated machines
An O(log n) ratio for undirected multicut.
Directed Multicut and ratio 3/2 for Multiway Cut
A ratio of 2 for the Steiner Network problem
Positive Semi-Definite approximation for Max-Cut and 3-coloring

Book of the course: There is a book by Vazirani and a book by
Shmoys and williamson whose pdf is public
A lot of the above it taken from a book by Ravi et al
See a PDF version on the homeppage of R. Ravi.

You will be able to get along without buying
any book

1) 5 Exercises 50 percent
2) Take Home Exam: Fifty percent

The Lecture notes

1) Class 1: Introduction to LP

2) Class 2: A sketch of the Ellipsoids algorithm

3) Class 3: Strong duality and minimum spanning trees

4) An exact algorithm for the assignment problem

5) An exact algorithm vertex cover and maximum matching on bipartite graph

6) Basic combinatorial approximation algorithms

7)Dual-fitting and primal dual for Set Cover

8) The submodular cover problem

9) Primal dual for Steiner Forest problem

10) An approximation ratio for facility location via filtering.

11) Local search

12) Randomized rounding

13) Scheduling unrelated machines

14) The simple O(log n) approximated for undirected multicut

15) Directed Multicut and 3/2 ratio for Multiway cut

16) A ratio 2 for Steiner Network.

17) PSD for Max Cut and 3-coloring.