Algorithms (F2008)

More flows ! PDF, LaTeX.

I’ll be using Chapter 11 from the textbook as a guide for our journey through approximation algorithms. However, I’d like to set the foundations with some basic material that I’ll draw from other sources. Since I don’t have comprehensive lecture notes yet, here are some links, with page numbers to look at:

• Rajeev Motwani’s (old) lecture notes on approximation algorithms. The notes are old, but the fundamentals haven’t really changed. I’ll be drawing on material from Chapter 1 (pages 1-33: the definitions, and the impossibility results).
• Sariel Har-Peled’s notes on approximation algorithms. The relevant material is in pages 1-2 (the greedy approximation algorithm for VERTEX COVER)

We practised reductions for a number of problems. First of all, I showed how to prove that Independent Set is NP-Complete, assuming that 3SAT is. The proof has a number of steps:

1. Show that Independent Set is in NP, by demonstrating that a guessed solution can be verified in polynomial time
2. Construct a transformation f that takes an arbitrary instance x of 3SAT and maps it to an instance f(x) of Independent Set, and does this in polynomial time.
3. Show that if x is satisfiable, then f(x) has an independent set of size k
4. Show that if f(x) has an independent set of size k, then x is satisfiable.

After that, we broke out into groups and looked at a number of NP-Completeness proofs. The problems we considered were:

• SAT (via CIRCUIT SAT)
• 3SAT (via SAT)
• SET PACKING (via INDEPENDENT SET)
• Not-All-Equal SAT (via SAT)
• TSP (via Hamiltonian Path)
• HITTING SET (via SET COVER via VERTEX COVER)

Not-All-Equal SAT is SAT, but where a clause must be satisfied without setting all literals to 1. All the other problems are defined in the textbook.

All of you worked on at least one of these problems, but I encourage you to try your hand at the others. You can be fairly sure that I’ll be asking some NP-Completeness questions either in an assignment or in the final.

On drawing pictures:

• Here’s a sample latex source file (and the picture used). Note that you MUST compile the source using pdflatex rather than latex. You can also use .pdf or .jpg files (just change the filename in the source)
• For drawing pictures, you can use
  • Ipe,  which integrates with LaTeX and generates PS or PDF
  • Xfig, which exports all kinds of formats (X-windows based)
  • Inkscape, which is an open source variant of Illustrator
  • Powerpoint (exports jpg)
  • Paint (exports jpg)
  • Or any program you like, and then use ‘convert’ on the CADE machines to convert it. For example, convert foo.bmp foo.jpg

  If you’re pressed for time, Powerpoint is the easiest solution. Long-term, Ipe and Inkscape are the best free solutions for drawing, and Ipe is the best if you have complicated LaTeX in the figure. Inkscape gives prettier pics though. My flow diagram was drawn in Ipe, but the range searching pic was drawn in Inkscape.

On assumptions for Q2:

• You can assume that operations involving a constant number of points and lines (do two lines intersect, and what is their intersection ? are two lines parallel ? What side of the line does this point lie on ? etc) can be performed in constant time, and you don’t need to specify how exactly this is done. If in doubt, post a comment and I’ll tell you if it’s ok to assume it.

Due Oct 27, 2008. PDF, LaTeX (edit the figure out to compile it)

The CADE name for submissions is ‘midterm’

If we have an NP-Complete problem X, then we can show that a new problem Y is NP-Complete by

• Showing that Y is in NP
• Showing that X reduces to Y.

But where did this first NP-Complete problem come from, if there aren’t turtles all the way down…

The answer is the Cook-Levin Theorem, one of the most profound results in complexity theory:

CIRCUIT-SAT is NP-Complete

We’ll handwave a proof of this, and look at some examples to understand how the proof works.

Mean: 88.32
Median: 95
StdDev: 20.02
Max: 100

Material for this lecture is drawn from Chapter 8 of the textbook, and archives of Ronald Reagan’s speeches on the Cold War.

Thus far we’ve been looking at techniques for designing efficient algorithms for problems. We’ll now stare failure in the face, and try to understand when we might fail at doing this, and why. In order to do so, we’ll reason about entire classes of problems at a time, rather than about a single problem. The central question of study is the (in)famous question: Is P = NP ?

We’ll consider two applications of max flows: image segmentation (Chapter 7.10), and analyzing playoff scenarios in league sports (NBA, NFL, MLB, etc) (Chapter 7.12)

We looked at the problem of computing a maximum matching in a bipartite graph, and showed that a simple max flow formulation yields the optimal matching. As an aside, I asked you to consider the following strategy:

Take any edge that doesn’t intersect the set of edges chosen thus far.

How badly might this do ?

We also saw that Hall’s theorem, a structural way of characterizing the existence of a perfect matching in a bipartite graph, can be proved using flow principles.

Finally, we examined some variants of the max flow problem that can all be reduced to the standard formulation. These were:

• circulations: having multiple sources and sinks, each with their own specified demands
• Lower bounds on edge capacities (like lower limits on speeds on a highway)
• Vertex capacities: limiting the amount of flow through a vertex (for example, this can arise when you have a warehouse that’s storing shipments, but can only store a limited amount of material)

The first two sections are taken from Section 7.5 of the text, and the last part is taken from Section 7.7.