Online algorithms with advice: the tape model
From MaRDI portal
Publication:529045
DOI10.1016/j.ic.2017.03.001zbMath1370.68334OpenAlexW2595319805MaRDI QIDQ529045
Hans-Joachim Böckenhauer, Rastislav Královič, Tobias Mömke, Richard Královič, Dennis Komm
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
job shop schedulingcompetitive analysispagingadvice complexityonline computationdisjoint path allocation
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (21)
Further Results on Online Node- and Edge-Deletion Problems with Advice ⋮ Call admission problems on grids with advice ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ Advice Complexity of Fine-Grained Job Shop Scheduling ⋮ Call admission problems on trees ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ Relative Worst-Order Analysis: A Survey ⋮ Length-Weighted Disjoint Path Allocation ⋮ Parallel solutions for ordinal scheduling with a small number of machines ⋮ 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 ⋮ The secretary problem with reservation costs ⋮ Advice Complexity and Barely Random Algorithms ⋮ Online node- and edge-deletion problems with advice ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ On the advice complexity of the online dominating set problem ⋮ Advice complexity of priority algorithms ⋮ Online Minimum Spanning Tree with Advice ⋮ Online bin covering with advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online computation with advice
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Competitive snoopy caching
- An efficient algorithm for the job-shop problem with two jobs
- Semi on-line algorithms for the partition problem
- Competitive paging with locality of reference
- On online algorithms with advice for the \(k\)-server problem
- Online makespan minimization with parallel schedules
- On the advice complexity of the \(k\)-server problem
- On Advice Complexity of the k-server Problem under Sparse Metrics
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- On the Advice Complexity of the k-Server Problem
- Disjoint Path Allocation with Sublinear Advice
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Competitive paging algorithms
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- Advice Complexity and Barely Random Algorithms
- How Much Information about the Future Is Needed?
This page was built for publication: Online algorithms with advice: the tape model
