On the power of randomization in on-line algorithms
From MaRDI portal
Publication:1312184
DOI10.1007/BF01294260zbMath0784.68038OpenAlexW2056760235WikidataQ29028151 ScholiaQ29028151MaRDI QIDQ1312184
Publication date: 19 January 1994
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01294260
Related Items
Competitive randomized algorithms for nonuniform problems, MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling, Competitive algorithms for the weighted server problem, Revisiting the COUNTER algorithms for list update, Some further results on the maximal hitting times of trees with some given parameters, Online unit clustering and unit covering in higher dimensions, The weighted 2-server problem, Randomized online multi-threaded paging, New on-line algorithms for the page replication problem, Page migration with limited local memory capacity, On multi-threaded metrical task systems, Fixed interval scheduling: models, applications, computational complexity and algorithms, Improved lower bounds for the online bin stretching problem, Improved analysis of the online set cover problem with advice, Non-greedy online Steiner trees on outerplanar graphs, The Value of Randomized Solutions in Mixed-Integer Distributionally Robust Optimization Problems, Extremal hitting times of trees with some given parameters, Randomized algorithms for metrical task systems, A competitive analysis of the list update problem with lookahead, On-line scheduling with hard deadlines, Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions, Two-stage security screening strategies in the face of strategic applicants, congestions and screening errors, Online max-min fair allocation, Expected linear round synchronization: the missing link for linear Byzantine SMR, Advice complexity of adaptive priority algorithms, Optimal randomized algorithm for a generalized ski-rental with interest rate, Competitive analysis for online leasing problem with compound interest rate, Competitive strategy for on-line leasing of depreciable equipment, On the (reverse) cover cost of trees with some given parameters, The \(k\)-server problem, Competitive distributed file allocation., Tight bounds for online coloring of basic graph classes, On the on-line rent-or-buy problem in probabilistic environments, On packet scheduling with adversarial jamming and speedup, A combined BIT and TIMESTAMP algorithm for the list update problem, Linear bounds for on-line Steiner problems, On convex body chasing, Distributed transactional memory for general networks, Randomized priority algorithms, Dynamic location problems with limited look-ahead, A universal randomized packet scheduling algorithm, Ramsey-type theorems for metric spaces with applications to online problems, Randomized competitive algorithms for online buffer management in the adaptive adversary model, Randomized Algorithms for Buffer Management with 2-Bounded Delay, A new lower bound for the list update problem in the partial cost model, On page migration and other relaxed task systems, Online algorithms for page replication in rings, On the Bahncard problem, Online \(k\)-taxi via double coverage and time-reverse primal-dual, Online \(k\)-taxi via double coverage and time-reverse primal-dual, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Resource Management in Large Networks, Randomized online interval scheduling, An adaptive probabilistic algorithm for online \(k\)-center clustering, On the competitiveness of the move-to-front rule, Competitive Algorithms for Layered Graph Traversal, Tight Bounds for Online Coloring of Basic Graph Classes, Randomized algorithm for the \(k\)-server problem on decomposable spaces, Randomized distributed online algorithms against adaptive offline adversaries, Optimal on-off control for a class of discrete event systems with real-time constraints, A Survey of Algorithms and Models for List Update, On randomization in on-line computation., A general decomposition theorem for the \(k\)-server problem, Competitive strategies for an online generalized assignment problem with a service consecution constraint, Online knapsack revisited, Memoryless algorithms for the generalized k-server problem on uniform metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strongly competitive randomized paging algorithm
- Competitive snoopy caching
- Borel determinacy
- Competitive \(k\)-server algorithms
- Random walks on weighted graphs and applications to on-line algorithms
- Competitive algorithms for server problems
- Competitive paging algorithms
- An optimal on-line algorithm for metrical task system
