Online algorithms with advice: the tape model

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

zbMATH Keywords

job shop schedulingcompetitive analysispagingadvice complexityonline computationdisjoint path allocation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

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