An experimental study of random knapsack problems

DOI10.1007/S00453-005-1193-7MaRDI QIDQ2369879zbMATH OpenOpenAlexFDO

Authors Rene Beier, Berthold Vöcking

Publication date 21 June 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-005-1193-7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Stochastic programming (90C15)

Recommendations

• Algorithms – ESA 2004
• Random knapsack in expected polynomial time
• Random knapsack in expected polynomial time
• Probabilistic analysis of knapsack core algorithms
• Probabilistic Analysis of the Multidimensional Knapsack Problem

Cites work

• scientific article; zbMATH DE number 1670670 (Why is no real title available?)
• scientific article; zbMATH DE number 4057285 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A minimal algorithm for the multiple-choice knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• Computing Partitions with Applications to the Knapsack Problem
• Discrete dynamic programming and capital allocation
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Multicriteria optimization
• Multiple criteria optimization: State of the art annotated bibliographic surveys
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Random knapsack in expected polynomial time

Cited in

(6)

• Random knapsack in expected polynomial time
• Smoothed analysis of integer programming
• Algorithms – ESA 2004
• Asymptotic behavior of the quadratic knapsack problem
• Random knapsacks with many constraints
• Random knapsack in expected polynomial time

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: An experimental study of random knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369879)