Online algorithms with advice: the tape model
DOI10.1016/J.IC.2017.03.001zbMATH Open1370.68334OpenAlexW2595319805MaRDI QIDQ529045FDOQ529045
Authors: Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, Tobias Mömke 
Publication date: 18 May 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.03.001
Recommendations
competitive analysisadvice complexityjob shop schedulingonline computationpagingdisjoint path allocation
Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)
Cites Work
- Title not available (Why is that?)
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Advice complexity and barely random algorithms
- Online computation with advice
- Competitive paging with locality of reference
- Competitive snoopy caching
- Competitive paging algorithms
- Semi on-line algorithms for the partition problem
- On advice complexity of the \(k\)-server problem under sparse metrics
- How Much Information about the Future Is Needed?
- On online algorithms with advice for the \(k\)-server problem
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- An efficient algorithm for the job-shop problem with two jobs
- Online makespan minimization with parallel schedules
- On the advice complexity of the \(k\)-server problem
- On the power of advice and randomization for the disjoint path allocation problem
- Advice complexity for a class of online problems
- Disjoint path allocation with sublinear advice
- Randomization can be as helpful as a glimpse of the future in online computation
- Job shop scheduling with unit length tasks: bounds and algorithms
Cited In (36)
- Online makespan scheduling with sublinear advice
- Advice complexity and barely random algorithms
- On the list update problem with advice
- On the advice complexity of the online dominating set problem
- Advice complexity of fine-grained job shop scheduling
- The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
- Computing with advice: when knowledge helps
- Disjoint path allocation with sublinear advice
- Randomization can be as helpful as a glimpse of the future in online computation
- Length-Weighted Disjoint Path Allocation
- Call admission problems on grids with advice
- Fully Online Matching with Advice on General Bipartite Graphs and Paths
- On the advice complexity of buffer management
- Online Minimum Spanning Tree with Advice
- Advice complexity and barely random algorithms
- Parallel solutions for ordinal scheduling with a small number of machines
- Towards using the history in online computation with advice
- Advice complexity of adaptive priority algorithms
- Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems
- Online knapsack with removal and recourse
- A technique to obtain hardness results for randomized online algorithms -- a survey
- Advice complexity of priority algorithms
- Relative Worst-Order Analysis: A Survey
- Online bin covering with advice
- Title not available (Why is that?)
- On energy-efficient computations with advice
- Priority algorithms with advice for disjoint path allocation problems
- How Much Information about the Future Is Needed?
- Call admission problems on trees
- On the power of randomness versus advice in online computation
- The secretary problem with reservation costs
- Quantum online algorithms with respect to space and advice complexity
- Further results on online node- and edge-deletion problems with advice
- Online node- and edge-deletion problems with advice
- Advice complexity of the online search problem
- Parallel solutions for preemptive makespan scheduling on two identical machines
This page was built for publication: Online algorithms with advice: the tape model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q529045)
