Disjoint path allocation with sublinear advice

DOI10.1007/978-3-319-21398-9_33zbMATH Open1465.68103OpenAlexW2242387516MaRDI QIDQ3196403FDOQ3196403

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

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

Recommendations

• On the power of advice and randomization for the disjoint path allocation problem
• Advice complexity of disjoint path allocation
• Advice complexity for a class of online problems
• Length-Weighted Disjoint Path Allocation
• The advice complexity of a class of hard online problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On online algorithms with advice for the \(k\)-server problem
• On the advice complexity of the \(k\)-server problem
• Title not available (Why is that?)
• 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
• Online computation with advice
• The tail of the hypergeometric distribution
• Title not available (Why is that?)
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• On advice complexity of the \(k\)-server problem under sparse metrics
• On the power of advice and randomization for the disjoint path allocation problem
• Online algorithms with advice: the tape model

Cited In (12)

• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• On the power of advice and randomization for the disjoint path allocation problem
• Length-Weighted Disjoint Path Allocation
• Call admission problems on grids with advice
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Online graph coloring against a randomized adversary
• Online interval scheduling with predictions
• On the advice complexity of the \(k\)-server problem
• Advice complexity of disjoint path allocation
• Priority algorithms with advice for disjoint path allocation problems
• Call admission problems on trees
• Online algorithms with advice: the tape model

This page was built for publication: Disjoint path allocation with sublinear advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196403)