Lecture 22 - Notes

April 4, 2016

Project Selection Problem

Imagine we have a set of projects $P$ with the following properties,

• Each project $v$ has an associated revenue $p_v$
• Each project has a set of requirements $E$ where $(v,w) \in E$ means you cannot do project $v$ unless you do project $w$
• A subset of projects, $A \subseteq P$ is feasible if the prerequisites for every project in $A$ are also in $A$.

The Problem: Given a set of project $P$ find a feasible solution that maximizes revenue.

Solution using Min-cut

To solve the set of projects,

• Assign a capacity of $\infty$ to all prerequisite edges
• Add an edge $(s,v)$ with capacity $p_v$ if the revenue is positive ($p_v \gt 0$)
• Add an edge $(v,t)$ with capacity $-p_v$ if the revenue is negative ($p_v \lt 0$)
• For convenience let $p_s$ and $p_t$ be zero.