Random knapsack in expected polynomial time

DOI10.1145/780542.780578zbMath1192.90157OpenAlexW2019110169MaRDI QIDQ5901087

Rene Beier, Berthold Vöcking

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780578

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (13)

An experimental study of random knapsack problems ⋮ New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ Smoothing the Gap Between NP and ER ⋮ Representation of the non-dominated set in biobjective discrete optimization ⋮ Sparse solutions to random standard quadratic optimization problems ⋮ Branch-and-bound solves random binary IPs in poly\((n)\)-time ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ On sparsity of the solution to a random quadratic optimization problem ⋮ Finding representations for an unconstrained bi-objective combinatorial optimization problem ⋮ An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times ⋮ Random knapsack in expected polynomial time ⋮ Average-case performance of rollout algorithms for knapsack problems

This page was built for publication: Random knapsack in expected polynomial time