A probabilistic analysis of the multiknapsack value function

DOI10.1007/BF01585741zbMath0694.90072OpenAlexW4246969534MaRDI QIDQ909581

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

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585741

zbMATH Keywords

probabilistic analysismultiknapsack problemstrong NP-hard

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09)

Related Items (10)

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ On rates of convergence and asymptotic normality in the multiknapsack problem ⋮ A class of generalized greedy algorithms for the multi-knapsack problem ⋮ Stochastic on-line knapsack problems ⋮ Average-case analysis of a greedy algorithm for the 0/1 knapsack problem. ⋮ The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem ⋮ A class of greedy algorithms for the generalized assignment problem ⋮ When two-constraint binary knapsack problem is equivalent to classical knapsack problem? ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• `` Strong NP-Completeness Results
• Convex Analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A probabilistic analysis of the multiknapsack value function