Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms
Characteristics influencing the efficiency of Lagrangean relaxation algorithms, such as the probability of the existence of \(\varepsilon\)- optimal and optimal \(\delta\)-feasible generalized saddle points of the Lagrange function, the magnitude of the duality gap, are investigated. The probabilistic analysis is conducted under the assumption that the coefficients of the multidimensional knapsack problem are independently distributed. In section 3 the author derives several general sufficient conditions of ``good asymptotic behaviour of the mentioned characteristics. In section 4 several specific classes of probabilistic models are introduced in detail. For each of these models explicit formulas for the optimal Lagrange multipliers are derived and sufficient conditions are expressed through the parameters of the model. In the last section a fast statistically efficient algorithm with linear running time for the approximate solution of the problem with random coefficients is presented. The paper is clearly and precisely written and can be highly recommended.
- A probabilistic analysis of the multiknapsack value function
- A Survey of Lagrangean Techniques for Discrete Optimization
- An approach to the construction of approximate solutions of Boolean linear programming problems
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
- scientific article; zbMATH DE number 3878679 (Why is no real title available?)
- scientific article; zbMATH DE number 4160471 (Why is no real title available?)
- scientific article; zbMATH DE number 4167855 (Why is no real title available?)
- scientific article; zbMATH DE number 3784631 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- Multi-constrained matroidal knapsack problems
- On rates of convergence and asymptotic normality in the multiknapsack problem
- Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
- Probabilistic analysis of the subset-sum problem
- Randomized algorithms in combinatorial optimization: A survey
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
- The multidimensional 0-1 knapsack problem: an overview.
- When two-constraint binary knapsack problem is equivalent to classical knapsack problem?
- scientific article; zbMATH DE number 4191399 (Why is no real title available?)
- scientific article; zbMATH DE number 4160471 (Why is no real title available?)
- scientific article; zbMATH DE number 4167855 (Why is no real title available?)
- scientific article; zbMATH DE number 4057284 (Why is no real title available?)
- The two-constraint binary knapsack problem's average case analysis for constraints with small, moderate and large coefficients
- The multidimensional 0-1 knapsack problem -- bounds and computational aspects
This page was built for publication: Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338142)
