Probabilistic analysis of knapsack core algorithms

MaRDI QIDQ5501294zbMATH OpenFDO

Authors Rene Beier, Berthold Vöcking

Publication date 3 August 2015

Mathematics Subject Classification ID

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

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)

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

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)