Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms

DOI10.1007/BF01581700zbMath0828.90090MaRDI QIDQ1338142

Igor Averbakh

Publication date: 27 November 1994

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

zbMATH Keywords

probabilistic analysisknapsack problemefficiency of Lagrangean relaxation algorithms

Mathematics Subject Classification ID

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

Related Items (3)

The multidimensional 0-1 knapsack problem: an overview. ⋮ When two-constraint binary knapsack problem is equivalent to classical knapsack problem? ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Randomized algorithms in combinatorial optimization: A survey
• Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
• Probabilistic analysis of the subset-sum problem
• On rates of convergence and asymptotic normality in the multiknapsack problem
• Multi-constrained matroidal knapsack problems
• An approach to the construction of approximate solutions of Boolean linear programming problems
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A Survey of Lagrangean Techniques for Discrete Optimization

This page was built for publication: Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms