COMS 482: unofficial class blog

Ford-Fulkerson Algorithm:

ford_fulkerson(G, s, t, capacity):
    f[e] = 0 for all e
    while there exists an s -> t path in the residual graph
        choose a path p
        f = augment(f, p)
        update residual graph
    Endwhile

augment(f, path):
    c = lowest capacity on path
    for each edge e on path
        if e if a forward edge
            f[e] += c
        if e is a backwards edge
            f[e] -= c
    Endfor

Termination:

Every time we find a path, the flow on s increases by at least 1 each time (assuming integer capacities). There is also a maximum possible flow from s, equal to C = sum( c_e ) of e out of s = f^out(s). We can find a path at most C times, so the total time = O( C * work to find and update path) = O(m*C).

Application: Bipartite Matching:

A Bipartite Matching is defined as V= X + Y where X & Y = {} and for all edges (a, b) in V, a is in X and b is in Y. Imagine wanting to assign people and tasks. You can create a network flow diagram for this:

Here, we draw an edge between a person and a task iff that person can perform said task. Then, running the flow algorithm will assign 1 person to every task, or find the best possible match. This runs in O(m*n) time, where m is the number of edges and n is the number of vertices.

• Source s with outflow only
• Source t with inflow only
• Directed graph with non-negative edge capacities

The goal is the minimize the flow from s -> t. A flow is a function f:E -> R+, from the edge set to amount of flow on that edge. We also define c_e to be the capacity of an edge e. To be a legal flow:

1. For each edge, 0 <= f(e) <= c_e
2. For each node v other than s, t, fⁱⁿ(v) = f^out(v)

The value of a flow f, v(f) = fⁱⁿ(t) = f^out(s) = sum( f(e) ) of e_out of s = sum( f(e) ) of e_in of t. As you’ve seen by now, fⁱⁿ(v) = sum( f(e) ) of e_in of v, and f^out(v) = sum( f(e) ) of e_out of v.

Here is an example of a network flow diagram:

Now, imagine pushing 18 units of flow across nodes {s, 1, 3, 4, t} to get the following flow diagram:

This is bad–it uses up too much of our capacity. The most we can push again from s -> t is only 2! Let’s allow the option of “undoing” an edge:

This is our redidual graph. Everywhere we have flow, we potentially have:

1. Some capacity left
2. Some “backflow” we can use to change our mind

Ford-Fulkerson Algorithm (Overview):

Find an s -> t path in graph
Update all flows
Make a new residual graph
Repeat

The following are topics for prelim 1:

• Stable matching
• Basic algorithms analysis
• Graphs
• Greedy algorithms
• Divide and conquer
• Dynamic programming

There will be 1-2 algorithms questions, and then some short answer questions about specific topics (Prim’s, Dijkstra’s).

On change detection in sequences of points. Segmented Least Squares with multi-way choices. Read section 6.3 in the book.

Algorithm:

For all pairs (i, j) | i <= j, compute the least squares error e_{i, j} for the segment p_i … p_j
C is a constant that defines the range of allowable error

For j = 1 to n
    For i = 1 to j
        OPT(j) = min(e_{i, j} + C + OPT(i-1));
    End For
EndFor

Return OPT(n)

Reasoning:

We partition the set of points into the set of all possible line segments. Then, for each line segment we compute the error of a least-squares fit through that line segment. Then, we iterate through all the line segments, finding the last point which has “acceptable” error, otherwise starting a new subsequence. In this way, we choose an optimal number and location of least squares fits for our data.

We’ve got a prelim on thursday–here are some study tips: www.cs.cornell.edu/courses/cs482/2005sp/review1.htm