How Much Information about the Future Is Needed?
From MaRDI portal
Publication:5448651
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
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