The online knapsack problem: advice and randomization

DOI10.1016/j.tcs.2014.01.027zbMath1282.68196OpenAlexW2025034398MaRDI QIDQ2437775

Peter Rossmanith, Hans-Joachim Böckenhauer, Richard Královič, Dennis Komm

Publication date: 13 March 2014

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

Full work available at URL: http://hdl.handle.net/20.500.11850/210420

zbMATH Keywords

randomizationknapsack problemadvice complexityonline computationresource augmentation

Mathematics Subject Classification ID

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

Related Items

Packing a Knapsack of Unknown Capacity, Further Results on Online Node- and Edge-Deletion Problems with Advice, Online Bin Packing with Advice of Small Size, Online Graph Coloring Against a Randomized Adversary, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Online algorithms with advice for the dual bin packing problem, On the advice complexity of the \(k\)-server problem, Optimal Online Edge Coloring of Planar Graphs with Advice, The advice complexity of a class of hard online problems, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Knapsack secretary through boosting, Online knapsack with removal and recourse, The secretary problem with reservation costs, Online two-way trading: randomization and advice, Online node- and edge-deletion problems with advice, Online algorithms with advice for bin packing and scheduling problems, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, On the advice complexity of the \(k\)-server problem under sparse metrics, On the advice complexity of the online dominating set problem, Advice Complexity of the Online Search Problem, Online bin packing with advice of small size, Improved online algorithm for fractional knapsack in the random order model, Online multi-coloring with advice, Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online removable knapsack with limited cuts
• Semi-online preemptive scheduling: one algorithm for all variants
• Online computation with advice
• Online removable square packing
• Online algorithms. The state of the art
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Online algorithms: a survey
• Online knapsack with resource augmentation
• Algorithmics for hard problems.
• Stochastic on-line knapsack problems
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• On the Advice Complexity of the Knapsack Problem
• On the Advice Complexity of the Set Cover Problem
• On the Advice Complexity of the k-Server Problem
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Speed is as powerful as clairvoyance
• Resource augmentation for online bounded space bin packing
• Reducibility among Combinatorial Problems
• Advice Complexity and Barely Random Algorithms
• Measuring the problem-relevant information in input
• Semi-online scheduling with decreasing job sizes
• Optimal time-critical scheduling via resource augmentation