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

Properties of several dual characteristics of the multidimensional knapsack problem (such as the probability of existence of ∈-optimal and optimal δ-feasible Lagrange function generalized saddle points, magnitude of relative duality gap, etc.) are investigated for different probabilistic models. Sufficient conditions of ‘good’ asymptotic behavior of the dual characteristics are given. A fast statistically efficient approximate algorithm with linear running time complexity for problems with random coefficients is presented.