Weighted online problems with advice
From MaRDI portal
Publication:726104
DOI10.1007/s00224-017-9806-5zbMath1391.68127arXiv1606.05210OpenAlexW2754371449MaRDI QIDQ726104
Joan. Boyar, Christian Kudahl, Jesper W. Mikkelsen, Lene Monrad Favrholdt
Publication date: 3 August 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.05210
Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Online algorithms; streaming algorithms (68W27)
Related Items (3)
Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Parallel solutions for ordinal scheduling with a small number of machines ⋮ On the advice complexity of the online dominating set problem
Cites Work
- Unnamed Item
- Online algorithms with advice for bin packing and scheduling problems
- Online computation with advice
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Competitive snoopy caching
- LRU is better than FIFO
- The advice complexity of a class of hard online problems
- Competitive paging with locality of reference
- Online makespan minimization with parallel schedules
- On the Advice Complexity of Online Problems
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- Advice Complexity of the Online Induced Subgraph Problem
- Measuring the problem-relevant information in input
- Online Bounded Analysis
This page was built for publication: Weighted online problems with advice