Graduate Algorithms

Perhaps the most important theorem in the study of flows is the max-flow min-cut theorem, which we will study in today’s lecture. In addition, we will also see an example application of flows to computing a maximum matching in a bipartite graph, and we will look at more efficient (and polynomial time) algorithms for computing max flows.

Additional reading: Some of the material covered today is best explained in these notes.

Aftermatter:

• Uri Zwick’s website: Presentation on Jenga, and the paper.
• An article by Brian Hayes that explains the result on stacking bricks.

This lecture covered the first few sections of Chapter 7 from the textbook. We learnt how to define a flow network, the notion of a maximum flow, how to construct an augmenting path, and the Ford Fulkerson algorithm.

Bondy and Murthy wrote a classic text on graph theory many years ago, and the book is now available online (scanned). If you are interested in a textbook on basic graph theory (that covers many of the basic graph structures we talk about in class), then this is a good reference to have.

The link is http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

Homework 3 is now online (pdf, latex). Remember that it is due next Monday, Oct 29.

Some comments:

• In the second problem, you are asked to show that heuristics for a poly-time solvable problem yield 2-approximations. It is not only NP-Complete problems that need approximations. Often, a problem can be solved exactly in polynomial time, but an approximation can be found much faster, and depending on the application, this might be acceptable.
• The final problem is a canonical example of how to prove that the planar version of a problem is NP-Complete: You take the problem, lay it out on the plane, and find some gadget that removes crossings while preserving whatever measure you’re trying to compute. Solving this problem will give you a good idea of how to attack any problem of this kind. A warning though: this problem will take some time, so don’t expect to be able to solve it on Sunday night without spending some time before then !

Update:  I’ve extended the assignment deadline to Oct 31, Wednesday, at 5pm.

The midterm can be found here. Due date is Oct 19 (friday) @ 5pm. LaTeX src (minus the figures: you’ll have to comment those parts out) is here.

Additional notes:

• You may NOT consult your fellow classmates or others. The books are your only friends.
• You may post questions about the midterm as comments on this post. I will be monitoring it frequently.

Today, we’ll cover linear programming, which apart from being one of the most important questions in operations research, is also a tool for generating lower bounds for NP-hard problems automatically. We’ll see how LPs can help us get a(nother) 2-approximation for Vertex Cover.

I’ve updated the class syllabus, populating the remaining lectures with a planned course of study in network flows, randomization, and an assortment of other topics. Also note two important date changes:

1. Homework 3 will now be handed out Oct 22 (rather than Oct 15), since you will all be busy with the midterm. However, the due date will remain the same.
2. The midterm will be two days long, rather than one day. Midterms will be due Friday Oct 19 @ 5pm (electronically or on paper)

Today’s lecture will continue our study of approximations. This time we will consider the travelling salesman problem in metric spaces  (Section 7.7 of these notes), and arbitrarily good approximations for KNAPSACK (KT 11).

In this lecture, we covered the simple 2-approximation for computing the vertex cover. In class, we proved the approximation ratio based on a simple local argument: namely that for each pair of vertices the algorithm chooses, OPT must pick at least one of them. We also looked at the problem of minimizing makespan which has the distinction of yielding one of the very first approximation algorithms, a 2-1/m approximation due to Ron Graham in 1966.

In both of the above cases, we emphasized the need for a lower bound on OPT, so as to reason about the approximation ratio guaranteed by our method. We were able to construct such a lower bound directly by inspection of the input or the algorithm. We then moved onto the problem of SET COVER, where such a lower bound is much harder to come by, and is constructed bit by bit from the steps of the algorithm.

The treatment of the SET COVER analysis in class differs slightly from the textbook. These notes are a useful guide to the method of analysis we used in class.