Weighted Online Problems with Advice

DOI10.1007/978-3-319-44543-4_14zbMath1391.68126OpenAlexW2431927087MaRDI QIDQ2819501

Christian Kudahl, Jesper W. Mikkelsen, Joan. Boyar, Lene Monrad Favrholdt

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://portal.findresearcher.sdu.dk/da/publications/0bb84106-9b1d-4f50-b50a-946eb95bf7e1

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 (4)

A survey on makespan minimization in semi-online environments ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ Online bin packing with advice of small size

Cites Work

• Unnamed Item
• 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
• Online makespan minimization with parallel schedules
• Advice Complexity of the Online Search Problem
• On the Advice Complexity of Online Problems
• Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
• Measuring the problem-relevant information in input
• Online Bounded Analysis

This page was built for publication: Weighted Online Problems with Advice