Beyond Competitive Analysis
From MaRDI portal
Publication:4507350
DOI10.1137/S0097539796299540zbMath0959.68131OpenAlexW2159472851MaRDI QIDQ4507350
Elias Koutsoupias, Christos H. Papadimitriou
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796299540
Related Items
Online-bounded analysis ⋮ On the relative dominance of paging algorithms ⋮ Quantifying Competitiveness in Paging with Locality of Reference ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Online network design with outliers ⋮ Scheduling search procedures: The wheel of fortune ⋮ Optimal eviction policies for stochastic address traces ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ Automated Credit Rating Prediction in a competitive framework ⋮ More on randomized on-line algorithms for caching. ⋮ A randomized algorithm for two servers in cross polytope spaces ⋮ Relative Worst-Order Analysis: A Survey ⋮ List update with probabilistic locality of reference ⋮ List factoring and relative worst order analysis ⋮ Unnamed Item ⋮ Online stochastic optimization under time constraints ⋮ The \(k\)-server problem ⋮ How much is it worth to know the future in online conversion problems? ⋮ Probabilistic analysis for scheduling with conflicts ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ On the Relative Dominance of Paging Algorithms ⋮ Coping with Incomplete Information in Scheduling — Stochastic and Online Models ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ The optimal structure of algorithms for \(\alpha\)-paging ⋮ Cost sharing mechanisms for fair pricing of resource usage ⋮ On the smoothness of paging algorithms ⋮ Online Vehicle Routing Problems: A Survey ⋮ On the power of lookahead in on-line server routing problems ⋮ Online Bounded Analysis ⋮ Knowledge state algorithms ⋮ Unnamed Item ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ Quantifying competitiveness in paging with locality of reference ⋮ Exact distributional analysis of online algorithms with lookahead ⋮ Discrete online TSP ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Engineering Efficient Paging Algorithms ⋮ On-line scheduling with monotone subsequence constraints ⋮ Unnamed Item ⋮ Parameterized analysis of paging and list update algorithms
