Online algorithms with advice for bin packing and scheduling problems
From MaRDI portal
Publication:496020
DOI10.1016/j.tcs.2015.07.050zbMath1329.68301arXiv1311.7589MaRDI QIDQ496020
Marc P. Renault, Rob van Stee, Adi Rosén
Publication date: 16 September 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.7589
machine scheduling; competitive analysis; online algorithms; bin packing; online computation with advice
90B35: Deterministic scheduling theory in operations research
90C27: Combinatorial optimization
68W27: Online algorithms; streaming algorithms
Related Items
Online bin covering with advice, Parallel solutions for preemptive makespan scheduling on two identical machines, Parallel solutions for ordinal scheduling with a small number of machines, Priority-based bin packing with subset constraints, Online bin packing with advice, Weighted online problems with advice, Algorithmic analysis of priority-based bin packing, A survey on makespan minimization in semi-online environments, Online algorithms with advice for the dual bin packing problem, The advice complexity of a class of hard online problems, Reordering buffer management with advice, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Online bin packing with advice of small size, Online makespan minimization with parallel schedules, Online two-dimensional vector packing with advice, Parallel online algorithms for the bin packing problem, Weighted Online Problems with Advice, A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey, Optimal Online Edge Coloring of Planar Graphs with Advice, Online Bin Packing with Advice of Small Size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for randomized on-line multiprocessor scheduling
- New lower bounds for certain classes of bin packing algorithms
- Online computation with advice
- Bin packing can be solved within 1+epsilon in linear time
- Does randomization help in on-line bin packing?
- A lower bound for randomized on-line scheduling algorithms
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- On online algorithms with advice for the \(k\)-server problem
- The online knapsack problem: advice and randomization
- On Advice Complexity of the k-server Problem under Sparse Metrics
- On the Advice Complexity of the k-Server Problem
- Reordering Buffer Management with Advice
- Online Bin Packing with Advice of Small Size
- On randomized online scheduling
- On the Advice Complexity of Online Problems
- Improved Bounds for the Online Scheduling Problem
- On the Advice Complexity of Buffer Management
- Online Makespan Scheduling with Sublinear Advice
- Advice Complexity and Barely Random Algorithms
- On-line machine covering
