Probabilistic analysis of knapsack core algorithms

MaRDI QIDQ5501294zbMATH OpenFDO

Authors Rene Beier, Berthold Vöcking

Publication date 3 August 2015

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• Random knapsack in expected polynomial time
• Random knapsack in expected polynomial time
• Core problems in knapsack algorithms
• A Minimal Algorithm for the 0-1 Knapsack Problem
• scientific article; zbMATH DE number 3904330

Cited in

(13)

• Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra
• An experimental study of random knapsack problems
• Core problems in knapsack algorithms
• scientific article; zbMATH DE number 4057284 (Why is no real title available?)
• Computing Optimized Path Integrals for Knapsack Feasibility
• Algorithms – ESA 2004
• Random knapsack in expected polynomial time
• On the integrality gap of binary integer programs with Gaussian data
• On the integrality gap of binary integer programs with Gaussian data
• Branch-and-bound solves random binary IPs in poly(n)-time
• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
• Smoothed analysis of integer programming
• Efficient heuristic algorithms for path-based hardware/software partitioning

This page was built for publication: Probabilistic analysis of knapsack core algorithms

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