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. Ax ≤ b, 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.