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

DOI10.1006/JAGM.1998.0954MaRDI QIDQ4225866zbMATH OpenOpenAlexFDO

Authors 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

OnLineGreedyzero-one knapsack problem

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 910873
• scientific article; zbMATH DE number 3904330
• Worst-case and average-case analysis of an algorithm solving a generalized knapsack problem
• The average-case analysis of some on-line algorithms for bin packing
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• Average-case performance of rollout algorithms for knapsack problems
• scientific article; zbMATH DE number 4057285
• scientific article; zbMATH DE number 1264402
• Multidimensional on-line bin-packing: An algorithm and its average-case analysis
• scientific article; zbMATH DE number 4047112

Cited in

(21)

• Stochastic on-line knapsack problems
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• Improved online algorithms for knapsack and GAP in the random order model
• Improved online algorithm for fractional knapsack in the random order model
• Online generalized assignment problem with historical information
• Average-case performance of rollout algorithms for knapsack problems
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Online knapsack revisited
• The online knapsack problem with incremental capacity
• scientific article; zbMATH DE number 4047112 (Why is no real title available?)
• scientific article; zbMATH DE number 4057285 (Why is no real title available?)
• Randomized algorithms for online knapsack problems
• Online unweighted knapsack problem with removal cost
• scientific article; zbMATH DE number 910873 (Why is no real title available?)
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Random knapsack in expected polynomial time
• A survey of online knapsack problems
• Online unbounded knapsack
• Smoothed analysis of integer programming
• On the sum minimization version of the online bin covering problem

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

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