A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs

Bruce Faaland
Additional contact information
Bruce Faaland: The University of Washington, Seattle, Washington

Operations Research, 1984, vol. 32, issue 2, 405-422

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 (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.2.405 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:2:p:405-422

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().