308-362B Winter 2005

January 6 Lecture: Course Overview and An Introduction to Linear Programming (Chapter 1 0f Chvatal,available at Copy-EUS).

January 11 Lecture: Stable Marriages: Section 1.1 of the text.

January 13th Lecture: Linear Programming Duality (Chapter 5 0f Chvatal, available at Copy-EUS).

January 18th Lecture: Five Representative Problems and Solutions to two of them. Sections 1.2, 4.1, 6.1 and 6.2 of the text.

January 20th Lecture: Lightest Paths in Graphs I. To prove that our algorithms for lightest paths were correct we relied on the following general approach for Lightest Path Certification. In this lecture, we began with the relatively simple Algorithm for Acyclic Directed Graphs. We discussed the fact that this algorithm could also find the heaviest path from a source $s$ to every vertex, and the use of this algorithm in the PERT (Problem Evaluation and Review Technique) for scheduling projects consisting of subtasks with precedence constraints.

January 25nd Lecture: Lightest Paths in Graphs II. We presented an Algorithm for General Directed Graphs. This algorithm is also discussed in Section 6.8 of the text.

January 27th Lecture: We discussed Johnson's O(nm) algorithm for determining if a graph contained negative cycles, including finding a negative cycle if one existed. This algorithm is discussed in Section 6.10 of the book. We then showed that we could use this algorithm to reduce the All Pairs Shortest Paths problem on graphs without negative cycles to the same problem on graphs without negative weight edges in $O(nm)$ time. We also began our discussion of Max Flow Problems.

February 1 Lecture: Maximum Flows I We described an algorithm for this problem and proved it terminated. This is sections 7.1 and 7.2 in the book. We showed how to decompose s-t flows up into a set of weighted s-t paths and cycles. That is we proved that for any flow $x$ in a capacitated network with $m$ arcs: for some $l \le m$ there is a set $C_1,,,.,.C_k$ of cycles and $P_{k+1}, ..., P_l$ and associated non-negative weights $w_1,..,w_l$ such that for each edge $e$, $x(e)$ is the sum of the weights of the cycles and paths containing $e$ and the volume of $x$ is the sum of the weights of the paths. We also showed that if the flow was integer valued then we could choose integer weights. This proof follows the lines of question 5 of assignment 2. We then showed that the if $x_1$ was a flow and $x_2$ was a maximum flow then there was a flow of volume $vol(x_2)-vol(x_1)$ in the auxiliary graph for $x_1$. Applying the previous result, we thereby obtained that there is a path of capacity $vol(x_2)-vol(x_1)/m$ in the auxiliary network. This implied that if we always augmented along a maximum capacity path in the auxiliarygraph we would perform only $O(m log (Cm))$ iterations where $C$ is the largest edge capacity. On the assignment, you were asked to show you could find such a path in $O(mlogm)$ time. This yields an implementation of our algorithm in $O(m squared log(m) log (Cm))$ time. A similar but different approach is taken in Section 7.3 of the book.

February 3 Lecture: Maximum Flows II We saw an application of the maximum flow algorithm to Bipartite Matching. This material can be found in Section 7.5 of the text. We mentioned some other applications which are not examined material.

February 8 Lecture: Maximum Flows III We saw extensions to the max flow problem, in particular circulations with demands and lower bounds (Section 7.7). This allowed us to see an example of such problems: Airline Scheduling (Section 7.9). We also started on another application of the max flow algorithm, Image Segmentation (Section 7.10). We will finish this problem this coming Thursday.

February 10 Lecture: We finished solving a special case of the Image Segmentation problem, namely classifying pixels as foreground or background of an image. We saw Dijkstra's $O(m)$ algorithm for finding lightest paths from $s$ to every other vertex in a graph with non-negative edge weights. I left the running time to be O(mlogn) but indeed, as Leonid and Nick pointed out, we can do better using a Fibonacci heap, namely O(nlogn + m). This becomes O(m) in graphs that are dense enough, where m > nlogn, i.e. m/n > log n, i.e. the average degree is larger than log n. Also Zhentao gave a presentation which is not examined material.

February 15 Lecture: Maximum Flows IV Material from this lecture will not be examined.

February 17: Midterm. Closed Book. No calculators or electronic aids allowed. In class.

March 1 Lecture: Proving a problem is hard We introduced a method for proving a problem is hard: we transform an instance of a known hard problem into an instance of our problem, in polynomial time (we were very careful in explaining what exactly we mean by "hard" and by "polynomial").

March 3 Lecture: Examples of polynomial-time reductions We went over the following polynomial-time reductions: Independent Set to Vertex Cover Independent Set to (the more general) Set Packing Vertex Cover to Independent Set Vertex cover to (the more general) Set Cover 3-SAT to Independent Set

March 8 Lecture: P, NP and NP-C We formalized the notions of running time and of an efficient checking algorithm. These led us to define the classes of problems P, NP, NP-C, and (briefly) CO-NP.

March 10 Lecture: Cook's Theorem We introduced the Cook-Levin Theorem and gave a direct proof of it: we showed Circuit-SAT is NP-Complete by considering any problem in NP and showing it can be polynomially reduced to Circuit-SAT.