Successful Greedy Algorithms in Linear Programming

SPEAKER: Alan Hoffman

IBM Research

ABSTRACT

A greedy algorithm for a linear programming problem is (by definition) successive maximization of variables chosen in some order. It rarely solves the problem, so it is appropriate to celebrate, and of some interest to classify, the unusual cases where a greedy algorithm succeeds.