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 nonze... View More