## 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.