Greedy packing and series-parallel graphs

Abstract

We characterize nonnegative matrices A with the following property: for every a ≧ 0, the linear programming problem max(1, y), where Ay ≦ 0, y ≧ 0, is solved by successively maximizing the variables in arbitrary order. The concept of series-parallel graphs is central to the characterization. © 1988.