Online knapsack revisited

DOI10.1007/S00224-014-9566-4zbMATH Open1333.90105DBLPjournals/mst/CyganJS16OpenAlexW1973221673WikidataQ59473381 ScholiaQ59473381MaRDI QIDQ260271FDOQ260271

Authors Marek Cygan, Łukasz Jeż, Jiří Sgall

Publication date 21 March 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-014-9566-4

zbMATH Keywords

online algorithmscompetitive analysisdual bin packingonline knapsack

Mathematics Subject Classification ID

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

Recommendations

• Online knapsack revisited
• Randomized algorithms for online knapsack problems
• Randomized algorithms for removable online knapsack problems
• Online minimization knapsack problem
• Online minimization knapsack problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1786227 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Fair versus unrestricted bin packing
• Maximizing job completions online
• On the advice complexity of the knapsack problem
• On the power of randomization in on-line algorithms
• Online knapsack with resource augmentation
• Online removable knapsack problem under convex function
• Prompt mechanism for ad placement over time
• Randomized algorithms for removable online knapsack problems
• Stochastic on-line knapsack problems
• Truthful Mechanisms via Greedy Iterative Packing

Cited in

(22)

• Online knapsack with resource augmentation
• Online Knapsack Problem Under Concave Functions
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• The online knapsack problem with incremental capacity
• Online Knapsack Problems with Limited Cuts
• Optimal Resource Augmentations for Online Knapsack
• Online unit profit knapsack with predictions
• Online knapsack revisited
• Randomized algorithms for removable online knapsack problems
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• Online budgeted maximum coverage
• Online knapsack problem under concave functions
• Online minimization knapsack problem
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Improved online algorithms for knapsack and GAP in the random order model
• Randomized algorithms for online knapsack problems
• Online algorithms with advice for the dual bin packing problem
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• A theory of auto-scaling for resource reservation in cloud services
• scientific article; zbMATH DE number 4047112 (Why is no real title available?)
• A simple PTAS for the dual bin packing problem and advice complexity of its online version
• Lower bounds on the performance of online algorithms for relaxed packing problems

This page was built for publication: Online knapsack revisited

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