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

Office hours: By appointment


Subjects covered:
Basic approximation algorithms
Approximation via LP rounding
A sketch of the Ellipsoids algorithm
A gentle introduction to strong duality
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
Scheduling unrelated machines
A simple 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
Lift and project methods

Book of the course: There is a book by Vazirani and a book by
Shmoys and williamson whose pdf is public

You will be able to get along without buying
the book

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

The Lecture notes

1) Class 1: Basic approximation algorithms

2) Class 2: A gentle introduction to LP and its relation to approximation

3) Class 3: A sketch of the Ellipsoids algorithm

4) Class 4: A gentle introduction to strong duality

5) Class 5: Dual Fitting and Primal Dual for Set Cover

6) Class 6: The submodular cover problem

7) Class 7: Primal dual for Steiner Forest problem

8) Class 8: A simple approximation ratio for facility location: filtering.

9) Class 9: Local search

10) Class 10: Randomized rounding

11) Class 11: Scheduling unrelated machines

12) Class 12: The simple O(log n) approximated for undirected multicut

13) Class 13: Directed Multicut and 3/2 ratio for Multiway cut

14) Class 14: A ratio 2 for Steiner Network.

15) Class 15: PSD for Max Cut and 3-coloring.

16) Lift and project approximation examples. To be added.