Advice Complexity and Barely Random Algorithms

DOI10.1007/978-3-642-18381-2_28zbMath1298.68116OpenAlexW1546040831MaRDI QIDQ3075527

Dennis Komm, Richard Královič

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2011__45_2_249_0/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Advice Complexity of Fine-Grained Job Shop Scheduling ⋮ Advice Complexity and Barely Random Algorithms ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles ⋮ On online algorithms with advice for the \(k\)-server problem ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient algorithm for the job-shop problem with two jobs
• Randomized competitive algorithms for the list update problem
• Competitive analysis of randomized paging algorithms
• On the power of randomization for job shop scheduling withk-units length tasks
• Online Computation with Advice
• On the Advice Complexity of Online Problems
• Advice Complexity and Barely Random Algorithms
• How Much Information about the Future Is Needed?

This page was built for publication: Advice Complexity and Barely Random Algorithms