Competitive algorithms for server problems
From MaRDI portal
Publication:3485852
DOI10.1016/0196-6774(90)90003-WzbMath0705.68023OpenAlexW2082099352WikidataQ63198876 ScholiaQ63198876MaRDI QIDQ3485852
No author found.
Publication date: 1990
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(90)90003-w
Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (only showing first 100 items - show all)
Competitive randomized algorithms for nonuniform problems ⋮ A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle ⋮ Lower bounds for on-line graph coloring ⋮ The list update problem and the retrieval of sets ⋮ A better lower bound on the competitive ratio of the randomized 2-server problem ⋮ The working set algorithm has competitive ratio less than two ⋮ A lower bound for two-server balancing algorithms ⋮ On-line algorithms for the dominating set problem ⋮ Uniform multipaging reduces to paging ⋮ A simple analysis of the harmonic algorithm for two servers ⋮ Randomized online computation with high probability guarantees ⋮ The weighted 2-server problem ⋮ The CNN problem and other \(k\)-server variants ⋮ On-line algorithms for weighted bipartite matching and stable marriages ⋮ A fast work function algorithm for solving the \(k\)-server problem ⋮ Online \(k\)-server routing problems ⋮ A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ Randomized online multi-threaded paging ⋮ Serving requests with on-line routing ⋮ Competitive algorithms for the on-line traveling salesman ⋮ The 2-evader problem ⋮ On multi-threaded metrical task systems ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Serving Online Requests with Mobile Servers ⋮ An on-line multi-CBR agent dispatching algorithm ⋮ Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ The orthogonal CNN problem ⋮ On the remote server problem or more about TCP acknowledgments ⋮ Randomized competitive analysis for two server problems ⋮ Approximation algorithms for clustering with dynamic points ⋮ Distributed near-optimal matching ⋮ On the additive constant of the \(k\)-server work function algorithm ⋮ Randomized algorithms for metrical task systems ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Constrained TSP and low-power computing ⋮ The minimum backlog problem ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Paging more than one page ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ More on randomized on-line algorithms for caching. ⋮ A randomized algorithm for two servers in cross polytope spaces ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Competitive strategy for on-line leasing of depreciable equipment ⋮ The \(k\)-server problem ⋮ More on weighted servers or FIFO is better than LRU. ⋮ Randomized Competitive Analysis for Two-Server Problems ⋮ The \(K\)-server problem via a modern optimization lens ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ ON THE k-TRUCK SCHEDULING PROBLEM ⋮ A note on the server problem and a benevolent adversary ⋮ Calculating lower bounds for caching problems ⋮ A comparison of performance measures for online algorithms ⋮ Online in-time service problem with minimal server assignment ⋮ SIMPLE: An optimal disk system with two restricted heads ⋮ Geometric two-server algorithms ⋮ Tight bounds for double coverage against weak adversaries ⋮ On the Additive Constant of the k-Server Work Function Algorithm ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ On Variants of File Caching ⋮ HARMONIC is 3-competitive for two servers ⋮ Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN ⋮ Benchmarking online dispatch algorithms for emergency medical services ⋮ The online graph bandwidth problem ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ The weighted list update problem and the lazy adversary ⋮ Online computation with advice ⋮ On metric clustering to minimize the sum of radii ⋮ Online chasing problems for regular polygons ⋮ Dynamic location problems with limited look-ahead ⋮ Two online algorithms for the ambulance systems ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Paging with request sets ⋮ Randomized algorithms for metrical task systems ⋮ Of robot ants and elephants: a computational comparison ⋮ A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem ⋮ A Randomized Algorithm for Two Servers in Cross Polytope Spaces ⋮ Online facility assignment ⋮ Managing multiple mobile resources ⋮ Unnamed Item ⋮ Multi-Finger Binary Search Trees ⋮ Better Bounds for Online Line Chasing ⋮ Paging more than one page ⋮ The combinatorics of effective resistances and resistive inverses ⋮ Unfair problems and randomized algorithms for metrical task systems ⋮ On the competitiveness of the move-to-front rule ⋮ Competitive analysis of randomized paging algorithms ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ The online \(k\)-server problem with rejection ⋮ On list update and work function algorithms. ⋮ The 3-server problem in the plane. ⋮ A randomized algorithm for two servers on the line. ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ The online \(k\)-server problem with max-distance objective ⋮ On the power of randomization in on-line algorithms ⋮ On-line algorithms for locating checkpoints ⋮ A new measure for the study of on-line algorithms ⋮ Online file caching with rejection penalties ⋮ A strongly competitive randomized paging algorithm ⋮ On lookahead in the list update problem ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics
This page was built for publication: Competitive algorithms for server problems
