This term I am teaching CS261, a graduate class on exact and approximate algorithms for combinatorial optimization problems.

I will largely follow the way Serge Plotkin designed the class: we start with simple examples of approximation algorithms for Vertex Cover, Set Cover, Steiner Tree and TSP, and notice how a key trick in each case is to find a way to upper bound the optimum.

Then we develop the basic theory of linear programming and duality, and show that: (i) if a rounding scheme can be found, we can use linear programming to design approximation algorithms and (ii) if one can guarantee that the optimum is integral then we can use linear programming to design exact algorithms. We get to (ii) in due time: we first develop combinatorial algorithms for max flow and bipartite matching, and then using linear programming to re-interpret such algorithms in terms of linear programming.

Finally, we talk about online algorithms, and here I will add to Serge’s material a couple of lectures on the secretary problem and on regret minimization when using expert advice.

The plan is to post here a summary of each lecture.

### Like this:

Like Loading...

*Related*