Weighted online problems with advice

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

zbMATH Keywords

schedulingonline algorithmsadvice complexityAOCweighted online problems

Mathematics Subject Classification ID

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