Course: Combinatorial optimization
Given by: Guy Kortsarz.
Office: 319 Business and Science Bldg.


Office hours: Wednesday 17:00-18:00

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

Book of the course: The lectures are based on slides.
A good book is Combinatorial Optimization by
Cook, Cunningham, Pulleyblanck and Schrijver

The lecture notes:

For a pdf file

Subjects covered:
Basics: Basic problems: Traveling sales person,
minimum spanning trees, maximum matchings, etc.
Flow networks: the flow along a cut,
the Ford-Fulkerson algorithm.
The min-cut max-flow theorem and the
Edmonds-Karp algorithm
Paths: shortest paths and BFS
Long paths: finding long paths via randomization.
Applications of flow: Finding a VC in bipartite graphs,
and half-integrality
Linear programming: duality and complementary slackness
Minimum spanning trees via duality
Solving linear programs:
The Ellipsoids algorithm.
The main ideas in the simplex algorithm,
programs with exponential number of constrains
Approximation algorithms, basics.
Approximating TSP and unweighted vertex cover
Approximating k-Center and weighted vertex cover
The set-cover problem, a greedy approximation
Dual fitting for set-cover

Credit:
1) Homework: 20%
2) Midterm 30%
3) Exam: 50%

Algorithms, exercises and handouts.

Theoretical exercises:
Exercise I: