Average-Case Analysis of Off-Line and On-Line Knapsack Problems

DOI10.1006/jagm.1998.0954zbMath0916.68069OpenAlexW4240438018MaRDI QIDQ4225866

George S. Lueker

Publication date: 17 January 1999

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1998.0954

zbMATH Keywords

zero-one knapsack problemOnLineGreedy

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (14)

The online knapsack problem with incremental capacity ⋮ Online knapsack of unknown capacity. How to optimize energy consumption in smartphones ⋮ Smoothed analysis of integer programming ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ Randomized algorithms for online knapsack problems ⋮ Online unweighted knapsack problem with removal cost ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ On the sum minimization version of the online bin covering problem ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Random knapsack in expected polynomial time ⋮ Average-case analysis of a greedy algorithm for the 0/1 knapsack problem. ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Online generalized assignment problem with historical information ⋮ Online knapsack revisited

This page was built for publication: Average-Case Analysis of Off-Line and On-Line Knapsack Problems