On rates of convergence and asymptotic normality in the multiknapsack problem

DOI10.1007/BF01586944zbMath0753.90045MaRDI QIDQ1181902

Leen Stougie, Sara van de Geer

Publication date: 27 June 1992

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

zbMATH Keywords

rate of convergenceasymptotic normalityLagrangean relaxationasymptotic characterizationmultiknapsack value function

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Integer programming (90C10) Boolean programming (90C09) Foundations of stochastic processes (60G05)

Related Items

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ A probabilistic analysis of the multi-period single-sourcing problem ⋮ 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 ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Probability inequalities for empirical processes and a law of the iterated logarithm
• Some limit theorems for empirical processes (with discussion)
• A probabilistic analysis of the multiknapsack value function
• Probabilistic analysis of the minimum weighted flowtime scheduling problem
• A class of generalized greedy algorithms for the multi-knapsack problem
• Exact Bounds for the Stochastic Upward Matching Problem
• A Concentration Inequality for the K-Median Problem
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Convergence of stochastic processes