Online knapsack revisited

DOI10.1007/s00224-014-9566-4zbMath1333.90105OpenAlexW1973221673WikidataQ59473381 ScholiaQ59473381MaRDI QIDQ260271

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

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

competitive analysisonline algorithmsdual bin packingonline knapsack

Mathematics Subject Classification ID

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

Related Items

A Theory of Auto-Scaling for Resource Reservation in Cloud Services, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Online algorithms with advice for the dual bin packing problem, Lower bounds on the performance of online algorithms for relaxed packing problems, Online knapsack of unknown capacity. How to optimize energy consumption in smartphones, Online minimization knapsack problem, A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version, Online Knapsack Problem Under Concave Functions, Online budgeted maximum coverage, Relaxing the irrevocability requirement for online graph algorithms, Online knapsack problem under concave functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fair versus unrestricted bin packing
• On the power of randomization in on-line algorithms
• Online knapsack with resource augmentation
• Stochastic on-line knapsack problems
• Online removable knapsack problem under convex function
• On the Advice Complexity of the Knapsack Problem
• Prompt Mechanism for Ad Placement over Time
• Truthful Mechanisms via Greedy Iterative Packing
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Maximizing job completions online
• Randomized Algorithms for Removable Online Knapsack Problems