A short proof of optimality of the bottom up algorithm for discrete resource allocation problems

DOI10.1016/S0167-6377(97)00026-6zbMath0893.90146MaRDI QIDQ1373462

J. Ning

Publication date: 19 November 1997

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

greedy algorithmresource allocationpolymatroidbottom up algorithmseparable concave function

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• On an optimization problem with nested constraints
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Submodular functions and optimization
• The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A short proof of optimality of the bottom up algorithm for discrete resource allocation problems