Online bin packing with advice
From MaRDI portal
Publication:261387
DOI10.1007/s00453-014-9955-8zbMath1336.68117arXiv1212.4016OpenAlexW2130428886MaRDI QIDQ261387
Shahin Kamali, Alejandro López-Ortiz, Kim S. Larsen, Joan. Boyar
Publication date: 23 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.4016
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)
Related Items (11)
Online algorithms with advice for the dual bin packing problem ⋮ The advice complexity of a class of hard online problems ⋮ Parallel solutions for ordinal scheduling with a small number of machines ⋮ Online two-dimensional vector packing with advice ⋮ Parallel online algorithms for the bin packing problem ⋮ A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version ⋮ On the advice complexity of the online dominating set problem ⋮ Lower bounds for several online variants of bin packing ⋮ Advice complexity of priority algorithms ⋮ Online bin covering with advice ⋮ Online bin packing with advice of small size
Cites Work
- Unnamed Item
- Unnamed Item
- Semi-on-line bin packing: a short overview and a new lower bound
- New lower bounds for certain classes of bin packing algorithms
- Semi-online scheduling revisited
- Online coloring of bipartite graphs with and without advice
- Online algorithms with advice for bin packing and scheduling problems
- On the list update problem with advice
- Online computation with advice
- Semi-on-line multiprocessor scheduling with given total processing time
- A fundamental restriction on fully dynamic maintenance of bin packing
- Bin packing can be solved within 1+epsilon in linear time
- Repacking helps in bounded space on-line bin-packing
- A linear time algorithm for restricted bin packing and scheduling problems
- The online knapsack problem: advice and randomization
- Algorithms for the Relaxed Online Bin-Packing Model
- Advice Complexity of Online Coloring for Paths
- On Online Algorithms with Advice for the k-Server Problem
- On the Advice Complexity of the Set Cover Problem
- Online Graph Exploration with Advice
- Online Coloring of Bipartite Graphs with and without Advice
- On the Advice Complexity of the k-Server Problem
- On Bin Packing with Conflicts
- On the online bin packing problem
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Advice Complexity of the Online Coloring Problem
- On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
- Polynomiality for Bin Packing with a Constant Number of Item Types
This page was built for publication: Online bin packing with advice