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

(13)

• 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
• Online graph coloring against a randomized adversary
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• On the advice complexity of the \(k\)-server problem
• Online interval scheduling with predictions
• Advice complexity of disjoint path allocation
• Online interval scheduling with predictions
• 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)