**Course:** Exact and Approximation algorithms

**Given by:**
Guy Kortsarz.

**Office: **319 Business and Science Bldg.

** Office hours:**
By appointment

**Url:**

http://crab.rutgers.edu/~guyk/courses.html

**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
**

**
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.
**

**
13) Scheduling unrelated machines
**

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

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