Probabilistic analysis of knapsack core algorithms

zbMATH Open1317.68291MaRDI QIDQ5501294FDOQ5501294

Authors: Rene Beier, Berthold Vöcking 

Publication date: 3 August 2015

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

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)

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
• Title not available (Why is that?)
• 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)