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 epsilon-optimal and optimal delta-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.