The online knapsack problem: advice and randomization
From MaRDI portal
Publication:2437775
DOI10.1016/j.tcs.2014.01.027zbMath1282.68196MaRDI 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
68W40: Analysis of algorithms
90C27: Combinatorial optimization
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Further Results on Online Node- and Edge-Deletion Problems with Advice, Packing a Knapsack of Unknown Capacity, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Knapsack secretary through boosting, Online knapsack with removal and recourse, Online bin packing with advice, Online algorithms with advice for bin packing and scheduling problems, On the advice complexity of the \(k\)-server problem under sparse metrics, Online algorithms with advice for the dual bin packing problem, The advice complexity of a class of hard online problems, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Online node- and edge-deletion problems with advice, On the advice complexity of the online dominating set problem, Improved online algorithm for fractional knapsack in the random order model, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Online two-way trading: randomization and advice, Online bin packing with advice of small size, Online multi-coloring with advice, On the advice complexity of the \(k\)-server problem, The secretary problem with reservation costs, Advice Complexity of the Online Search Problem, Optimal Online Edge Coloring of Planar Graphs with Advice, Online Graph Coloring Against a Randomized Adversary, Online Bin Packing with Advice of Small Size
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
