DMMP Seminar

DMMP Seminar

Walter Kern — Greedy Algorithms for Linear Programs

Time: Wednesday, May 12, 2010, 12:45-13:30
Location: Room 101, Citadel

The greedy algorithm for a linear program of the form max c x s.t. Axb, x ≥ 0 would first raise the variable with highest c-value until some constraint gets tight, then proceed with the second highest c-value etc. The class of {0,1}-matrices for which such a greedy approach always works can be characterized.

When trying to extend this result to {±1,0} matrices we came across a new greedy algorithm for max flow whose complexity is still unexplored.