An experimental study of random knapsack problems

DOI10.1007/S00453-005-1193-7zbMATH Open1117.90061OpenAlexW2142028613MaRDI QIDQ2369879FDOQ2369879

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

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)