Disjoint Path Allocation with Sublinear Advice
From MaRDI portal
Publication:3196403
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
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