Probabilistic analysis of the subset-sum problem
From MaRDI portal
Publication:1168896
DOI10.1016/0166-218X(82)90055-5zbMath0493.90066MaRDI QIDQ1168896
Claude Puech, Gianfranco D'Atri
Publication date: 1982
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
probabilistic analysisrandom coefficientsknapsack problems0-1 linear programminggreedy-like algorithmsthe subset-sum problem
Numerical mathematical programming methods (65K05) Linear programming (90C05) Stochastic programming (90C15) Boolean programming (90C09)
Related Items (7)
The bounded subset sum problem is almost everywhere randomly decidable in O(n) ⋮ Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations ⋮ The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem ⋮ Random knapsack in expected polynomial time ⋮ Average-case performance of rollout algorithms for knapsack problems ⋮ Approximation schemes for the subset-sum problem: Survey and experimental analysis
Cites Work
This page was built for publication: Probabilistic analysis of the subset-sum problem
