Randomized algorithms for online knapsack problems

DOI10.1016/j.tcs.2014.10.017zbMath1303.68160OpenAlexW1980280644MaRDI QIDQ476887

Kazuhisa Makino, Yasushi Kawase, Xin Han

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.017

zbMATH Keywords

competitive analysisknapsack problemrandomized algorithmonline algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

Packing a Knapsack of Unknown Capacity, The online knapsack problem with incremental capacity, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Online knapsack of unknown capacity. How to optimize energy consumption in smartphones, Learning-augmented algorithms for online subset sum, Online minimization knapsack problem, Proportional cost buyback problem with weight bounds, Online Knapsack Problem Under Concave Functions, Improved Online Algorithms for Knapsack and GAP in the Random Order Model, Online budgeted maximum coverage, Improved online algorithms for Knapsack and GAP in the random order model, Relaxing the irrevocability requirement for online graph algorithms, Online knapsack problem under concave functions, Unit cost buyback problem, Online Submodular Maximization Problem with Vector Packing Constraint., Improved online algorithm for fractional knapsack in the random order model, Online generalized assignment problem with historical information

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stochastic on-line knapsack problems
• Constant-Time Approximation Algorithms for the Knapsack Problem
• Online Knapsack Problem with Removal Cost
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Online Knapsack Revisited
• Online Minimization Knapsack Problem
• A Knapsack Secretary Problem with Applications
• Optimal Resource Augmentations for Online Knapsack
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Randomized Algorithms for Removable Online Knapsack Problems
• Algorithms – ESA 2005