Disjoint path allocation with sublinear advice

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

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

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 (9)

• The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
• Length-Weighted Disjoint Path Allocation
• Call admission problems on grids with advice
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Online interval scheduling with predictions
• On the advice complexity of the \(k\)-server problem
• Online Graph Coloring Against a Randomized Adversary
• 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)