PDF of Eric’s written notes are here.

**Max-flow via Linear Programming**

Variables for every . Objective function: . Constraints: for every , , for every , .

**Standard form for LP**

variables , constraints , objectives , and . We want to maximize subject to . (for example refer to the written notes)

** Primal LP Dual LP**

So dual(dual)=primal.

For a LP, optimum is achieved at a vertex of the feasible region except if

- it’s infeasible (e.g.: & ), so feasible region is empty
- it’s unbounded (e.g.: s.t. )

**Weak duality theorem**

For a LP whose primal and dual are feasible, their optimum and satisfy

Consequence: if we have a feasible of primal LP and a feasible of dual LP, and , then and are optimal solutions.

**Strong duality theorem**

If primal LP has optimal and dual LP has optimal , then .

If primal LP is unbounded, then dual LP is infeasible.

If dual LP is unbounded, then primal LP is infeasible.

**Line fitting**

Given points , find the line which minimizes the maximum distance.

Variables: . Goal: minimize where for all ,

**Example**: .

LP Problem: variables , minimize s.t.

In standard form, maximize , s.t.

How to get nonnegative constraints? Make variables , and replace .

New LP becomes: maximize s.t.