Disjoint path allocation with sublinear advice

DOI10.1007/978-3-319-21398-9_33MaRDI QIDQ3196403zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1003262 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1404324 (Why is no real title available?)
• Advice complexity and barely random algorithms
• Information complexity of online problems
• Measuring the problem-relevant information in input
• On advice complexity of the \(k\)-server problem under sparse metrics
• On online algorithms with advice for the \(k\)-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of the \(k\)-server problem
• On the power of advice and randomization for the disjoint path allocation problem
• Online algorithms with advice: the tape model
• Online computation with advice
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• The tail of the hypergeometric distribution

Cited in

(12)

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

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)