A class of generalized greedy algorithms for the multi-knapsack problem

DOI10.1016/0166-218X(93)90051-OzbMath0785.90072OpenAlexW2077554072MaRDI QIDQ1803680

Leen Stougie, Alexander H. G. Rinnooy Kan, Carlo Vercellis

Publication date: 29 June 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90051-o

zbMATH Keywords

heuristicsupper boundapproximate solutionsworst casegeneralized greedy algorithmsmulti-knapsack problemprobabilistic performance analysis

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Related Items (13)

Constrained multi-project planning problems: A Lagrangean decomposition approach ⋮ The air-cargo consolidation problem with pivot weight: models and solution methods ⋮ Revenue management in make-to-order manufacturing-an application to the iron and steel industry ⋮ Network capacity control using self-adjusting bid-prices ⋮ Connectivity and stochastic robustness of synchronized multi-drone systems ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ On rates of convergence and asymptotic normality in the multiknapsack problem ⋮ Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures ⋮ A probabilistic analysis of the multi-period single-sourcing problem ⋮ A class of greedy algorithms for the generalized assignment problem ⋮ An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition ⋮ A Markov model for single-leg air cargo revenue management under a bid-price policy ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• A probabilistic analysis of the multiknapsack value function
• Stochastic on-line knapsack problems
• Two Lines Least Squares
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: A class of generalized greedy algorithms for the multi-knapsack problem