Competitive randomized algorithms for nonuniform problems
From MaRDI portal
Publication:1329146
DOI10.1007/BF01189993zbMath0806.68053OpenAlexW3137684744MaRDI QIDQ1329146
L. A. McGeoch, M. S. Manasse, Anna R. Karlin, Susan Owicki
Publication date: 13 February 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01189993
Related Items
The working set algorithm has competitive ratio less than two ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Randomized online multi-threaded paging ⋮ Machine learning advised ski rental problem with a discount ⋮ Randomized competitive analysis for two server problems ⋮ Randomized algorithms for metrical task systems ⋮ Stochastization of Weighted Automata ⋮ Non-linear ski rental ⋮ Joint replenishment meets scheduling ⋮ Nearly optimal strategies for special cases of on-line capital investment. ⋮ 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 ⋮ Dynamic Balanced Graph Partitioning ⋮ The \(k\)-server problem ⋮ On the on-line rent-or-buy problem in probabilistic environments ⋮ Price Fluctuations: To Buy or to Rent ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Metrical service systems with multiple servers ⋮ Randomized algorithms for metrical task systems ⋮ Unnamed Item ⋮ On the best possible competitive ratio for the multislope ski-rental problem ⋮ Impatient Online Matching ⋮ Unfair problems and randomized algorithms for metrical task systems ⋮ USING STOCHASTIC INFORMATION TO PREDICT APPLICATION BEHAVIOR ON CONTENDED RESOURCES ⋮ Machine learning advised algorithms for the ski rental problem with a discount ⋮ Randomized strategies for non-additive 3-slope ski rental ⋮ A randomized algorithm for two servers on the line. ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ Rent or buy problems with a fixed time horizon ⋮ Online strategies for backups ⋮ Online dynamic power management with hard real-time guarantees
Uses Software
Cites Work
- Unnamed Item
- A strongly competitive randomized paging algorithm
- Competitive snoopy caching
- A competitive 2-server algorithm
- On the power of randomization in on-line algorithms
- Competitive \(k\)-server algorithms
- Random walks on weighted graphs and applications to on-line algorithms
- An Optimal On-Line Algorithm for K Servers on Trees
- New Ressults on Server Problems
- Competitive algorithms for server problems
- A New Approach to the Server Problem
- Competitive paging algorithms
- Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
- An optimal on-line algorithm for metrical task system
This page was built for publication: Competitive randomized algorithms for nonuniform problems
