CS330 HW08

Problem 1 §

As outlined in This Ed Discussion I assume I will have available the whole flow function at my disposal.

// Find the min-cut edges
// let f[e] the max-flow capacity by the flow function
// let e.cap be the capacity of edge e

RESIDUAL(V, E, f):
    let r_E = [] // for residual edges
    for edge e (u->v) in E:
        forward_res = e.cap - f[e] // forward residual capacity
        if forward_res > 0:
            add edge e (u->v) with e.cap = forward_res to r_E
        if f[e] > 0:
            add edge e' (v->u) with e'.cap = f[e] to r_E // Only add reverse edge if flow > 0
    return r_E

// Run DFS to find reachable vertices in residual graph
reachable = DFS(s, r_E)
unreachable = V - reachable

// Find min-cut edges
min_cut_E = []
for a in reachable:
    for b in unreachable:
        if edge e (a->b) in E:
            add e to min_cut_E

INCREMENT(e):
    if e not in min_cut_E:
        f[e] = f[e] + 1
    else:
        r_E = RESIDUAL(V, E, f)
        path = BFS(s, t, r_E) // augmenting path in res graph
        if path exists:
            augment_flow(path, 1) // flow augmentation from class
            // Augment flow along path by 1
    return f

DECREMENT(e):
    if f[e] > 0 and e in min_cut_E:
        f[e] = f[e] - 1
    else:
        r_E = RESIDUAL(V, E, f)
        path = BFS(s, t, r_E) // augmenting path in res graph
        if path exists:
            augment_flow(path, -1) 
            // Decrease flow along path by 1
    return f

Correctness §

• This leverages the correctness of the max-flow and min-cut algorithm

1. Increment function
   1. If the increment is in not in a min-cut the graph is still bottlenecked at the min-cut, and the maximum flow cannot increase. The flow function is the same
   2. If the increement is in the min-cut, there may be more flow to be had. T
      1. here is need only to construct and update using the residual network once because the increment is by 1, which means any path found by BFS on the residual graph is guaranteed to increase the max-flow.
      2. Alternatively, if the BFS doesn’t find any path in the residual network, this means that the graph has a different min-cut due to the capacity change. But the flow function wouldn’t change because there would be nothing to update (again, leveraging the correctness of the max-flow augmentation step.)
2. Decrement function
   1. If the decrement is in a min-cut the graph’s bottleneck is reduced. The max flow will be reduced by 1
   2. If the decrement is not in a min-cut the graph’s bottleneck is not reduced, but there may be a change in flow. Use the flow augmentation step (symmetric to the increment in-min-cut situation) to update the flow function

Complexity §

• Residual calculation: $O(V+E)$ but assume $V<E$ thus $O(E)$
• Using BFS shortest augmenting path: $O(E)$
• Total: $O(E)$

Problem 2 §

N = Set of visitors, where n in N is the set of demographics
// e.g. N[0] = {male, 40-50}

M = Set of advertisers and their preferences and number of ads
// e.g. M[0] = {male, female}, M[0].showCount = 3

// Construct graph G = (V,E) such that
for n in N:
	add n to V
for m in M:
	add m to V

// for every advertiser...
for m in M:
	// check if each visitor has any acceptable demographic
	for n in N:
		for dem in M:
			if n contains dem:
				add (n->m,1) to E // directed edge n->m weight 1

// Add start and end vertex for max-flow

add s, t to V
for n in N:
	add (s->n, 1)
for m in M:
	// by allowing bigger capacity here, required # of visitors
	// accessed by the advertisers
	add (m->t, m.showCount)

// Calculate the max-flow with algorithm from class
MaxFlow(G)

for every vertex m such that (m->t) in E:
	if edge (m->t) is at capacity:
		continue
	else // not at capacity; advertiser isn't satisfied
		return False
return true

Correctness §

• Idea is to transform the problem into the matching edges problem described in class, which is a variant of the max-flow problem

1. Visitor is guarateed to be shown only one ad, because $s\to n\in N$ has capacity $1$, meaning that for any edge $n\to m\in M$ only one of them can be used in max-flow (recall all edges $n\to m$ for any $n\in N,m\in M$ has capacity $1$)
2. Advertiser is guaranteeed to be shown their ad only to the right demographic group, due to the edge matching conditions in line 13-19.
3. If all edges $m\to t$ where $m\in M$ is at capacity, it means that the ads have the shown as much as the advertiser requested (showCount). This is because all edges $n\to m$ for any $n\in N,m\in M$ has capacity $1$, and thus max-flow must use showCount number of $n\to m$ edges for max-flow.
   1. Thus, if the max-flow algorithm ends up using the full capacity of these edges, the conditions of the problem are feasible
   2. Else, the advertisers requested showCount has not been satisfied and the conditions are not feasible.

Complexity §

• let $|N|=n,|M|=m$. Note that both $max(|M[i]|),max(|N[i]|)=O(k)$ where $k$ is the number of demographic groups
• Graph Construction: line 8-11 $O(n+m)$, line 14-19 $O(n\cdot m\cdot max(|M[i]|)\cdot max(|N[i]|))=O(nm{k}^2)$
• Max-flow using BFS shortest augmenting path: $O((n+m)(nm+n+m))$
  • $n+m+2$ is the number of vertices
  • $nm$ is the number of edges between $n\in N,m\in M$
  • $n+m$ is the number of edges between $s\to n$, $m\to t$
  • ⇒ Total $O(nm(n+m))$
• Checking $m\to t$ is at max capacity: $O(m)$
• Total: $O(nm(n+m+k^2))$