Measuring the problem-relevant information in input
From MaRDI portal
Publication:5321779
DOI10.1051/ita/2009012zbMath1176.68089OpenAlexW2112906671MaRDI QIDQ5321779
Rastislav Královič, Stefan Dobrev, Dana Pardubská
Publication date: 15 July 2009
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2009__43_3_585_0/
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Further Results on Online Node- and Edge-Deletion Problems with Advice, On the Power of Randomness versus Advice in Online Computation, Online Bin Packing with Advice of Small Size, Online Multi-Coloring with Advice, Online Graph Coloring Against a Randomized Adversary, Treasure Hunt with Advice, Disjoint Path Allocation with Sublinear Advice, On the advice complexity of the \(k\)-server problem, Improved analysis of the online set cover problem with advice, Optimal Online Edge Coloring of Planar Graphs with Advice, On the advice complexity of online bipartite matching and online stable marriage, The advice complexity of a class of hard online problems, Relative Worst-Order Analysis: A Survey, Length-Weighted Disjoint Path Allocation, Online minimum spanning trees with weight predictions, Advice complexity of adaptive priority algorithms, Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems, The online knapsack problem: advice and randomization, Online two-way trading: randomization and advice, Quantum online algorithms with respect to space and advice complexity, Online node- and edge-deletion problems with advice, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Weighted online problems with advice, Online Minimum Spanning Tree with Advice, On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles, Weighted Online Problems with Advice, Online bin packing with advice of small size, Advice complexity of maximum independent set in sparse and bipartite graphs, Online multi-coloring with advice, Online bin packing with advice
Cites Work
- Competitive snoopy caching
- A new measure for the study of on-line algorithms
- On the influence of lookahead in competitive paging algorithms
- A unified analysis of paging and caching
- Online algorithms: a survey
- Competitive analysis of randomized paging algorithms
- Competitive paging with locality of reference
- The Accommodating Function: A Generalization of the Competitive Ratio
- A Remark on Stirling's Formula
- Competitive paging algorithms
- On-Line Paging Against Adversarially Biased Random Inputs
- Nearly optimal FIFO buffer management for DiffServ
- Oracle size
- Distributed Computing with Advice: Information Sensitivity of Graph Coloring
- Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
- Lower and Upper Bounds on FIFO Buffer Management in QoS Switches
- Bounds for Certain Multiprocessing Anomalies
- Tree Exploration with an Oracle
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
