A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs

We solve a simple class of linear programming problems with tree-structured constraint matrices. Our procedure separates the problem into a sequence of continuous knapsack problems, each of which requires linear time to solve, for total solution time no worse than proportional to the number of nonzero entries in the original constraint matrix. The model arises in portfolio selection, advertising, and inventory and production planning.