On simple combinatorial optimization problems

Abstract

We characterize (0,1) linear programming matrices for which a greedy algorithm and its dual solve certain covering and packing problems. Special cases are shortest path and minimum spanning tree algorithms. © 1992.