A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
Operations Research · 1984 · Volume 32 · Issue 2
Abstract
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.
Keywords
637 weighted selection
Enable JavaScript for citation tools and additional paper interactions.