Max Flow and Parallel Algorithms

26 Mar 2014

###Problem 1

• Enforcing $\leq max$ constraint:

              o --------- o
       max   /             \
    s ----- o ----- o ----- t
  

###Problem 2

Edmonds-Karp algorithm - Compute maximum flow efficiently

###Problem 3

• Enforcing $\geq min$ constraint:

              o ----- o
       >=min /         \
            s           t
     sum-min \         / 
              o ----- o
  

###Problem 4

non-zero-sum game is weird

###Problem 5

• In the end, you’ll inevitably hit the bottleneck, one or another.
• In this problem, the bottleneck is memory bandwidth