Disjoint Path Allocation with Sublinear Advice

DOI10.1007/978-3-319-21398-9_33zbMath1465.68103OpenAlexW2242387516MaRDI QIDQ3196403

Richard Královič, Dennis Komm, Rastislav Královič, Jasmin Smula, Heidi Gebauer

Publication date: 29 October 2015

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

Full work available at URL: http://hdl.handle.net/20.500.11850/156333

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Call admission problems on grids with advice ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ On the advice complexity of the \(k\)-server problem ⋮ Call admission problems on trees ⋮ Fully Online Matching with Advice on General Bipartite Graphs and Paths ⋮ Length-Weighted Disjoint Path Allocation ⋮ Online interval scheduling with predictions ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ Online algorithms with advice: the tape model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online algorithms with advice: the tape model
• Online computation with advice
• The tail of the hypergeometric distribution
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• On Advice Complexity of the k-server Problem under Sparse Metrics
• On Online Algorithms with Advice for the k-Server Problem
• On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
• On the Advice Complexity of the k-Server Problem
• Information Complexity of Online Problems
• On the Advice Complexity of Online Problems
• Advice Complexity and Barely Random Algorithms
• Measuring the problem-relevant information in input

This page was built for publication: Disjoint Path Allocation with Sublinear Advice