How Much Information about the Future Is Needed?

DOI10.1007/978-3-540-77566-9_21zbMath1132.68422MaRDI QIDQ5448651

Stefan Dobrev, Rastislav Královič, Dana Pardubská

Publication date: 7 March 2008

Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_21

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

Online Matching in Regular Bipartite Graphs, Advice Complexity and Barely Random Algorithms, Towards using the history in online computation with advice, On Usefulness of Information: Framework and NFA Case, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Online knapsack with removal and recourse, Online coloring of bipartite graphs with and without advice, On the advice complexity of the \(k\)-server problem under sparse metrics, On the list update problem with advice, Online algorithms with advice: the tape model, Online computation with advice, The string guessing problem as a method to prove lower bounds on the advice complexity, Reordering buffer management with advice, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, On the advice complexity of the online dominating set problem, Exploring sparse graphs with advice, Call admission problems on grids with advice, Two-way and one-way quantum and classical automata with advice for online minimization problems, Online bin packing with advice of small size, On online algorithms with advice for the \(k\)-server problem, Improved analysis of the online set cover problem with advice, Advice Complexity of the Online Search Problem, A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey, Advice Complexity of Fine-Grained Job Shop Scheduling, On the Advice Complexity of the k-Server Problem, Advice Complexity and Barely Random Algorithms, On the Power of Randomness versus Advice in Online Computation