CS261

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s