An optimal on-line algorithm for metrical task system
From MaRDI portal
Publication:4302787
DOI10.1145/146585.146588zbMath0799.68035OpenAlexW2114538202WikidataQ29543421 ScholiaQ29543421MaRDI QIDQ4302787
Allan Borodin, Nathan Linial, Michael E. Saks
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/146585.146588
on-line algorithmsdynamic systemsmetrical task systemon-line scheduling algorithmuniform task system
Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (58)
Competitive randomized algorithms for nonuniform problems ⋮ A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle ⋮ Competitive algorithms for the weighted server problem ⋮ An improved lower bound for load balancing of tasks with unknown duration ⋮ Randomized online computation with high probability guarantees ⋮ On-line generalized Steiner problem ⋮ The CNN problem and other \(k\)-server variants ⋮ Randomized online multi-threaded paging ⋮ Uniform metrical task systems with a limited number of states ⋮ The complexity of mean payoff games on graphs ⋮ On multi-threaded metrical task systems ⋮ Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ Randomized algorithms for metrical task systems ⋮ On-line scheduling with hard deadlines ⋮ The complexity of mean payoff games ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Competitive vertex recoloring. (Online disengagement) ⋮ Expected linear round synchronization: the missing link for linear Byzantine SMR ⋮ The \(k\)-server problem ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ The \(K\)-server problem via a modern optimization lens ⋮ ON THE k-TRUCK SCHEDULING PROBLEM ⋮ Dynamic pricing of servers on trees ⋮ Nested convex bodies are chaseable ⋮ Parametrized Metrical Task Systems ⋮ Lower bounds in on-line geometric searching ⋮ Online computation with advice ⋮ Randomized priority algorithms ⋮ Online chasing problems for regular polygons ⋮ Competitive analysis for the on-line truck transportation problem ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Paging with request sets ⋮ Randomized algorithms for metrical task systems ⋮ A dynamic location problem for graphs ⋮ Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing ⋮ A new lower bound for the list update problem in the partial cost model ⋮ On page migration and other relaxed task systems ⋮ Unified Algorithms for Online Learning and Competitive Analysis ⋮ Better Bounds for Online Line Chasing ⋮ Algorithms for energy conservation in heterogeneous data centers ⋮ A Combinatorial Metrical Task System Problem Under the Uniform Metric ⋮ Exploiting problem structure in optimization under uncertainty via online convex optimization ⋮ Unfair problems and randomized algorithms for metrical task systems ⋮ On the competitiveness of the move-to-front rule ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ Topology matters: smoothed competitiveness of metrical task systems ⋮ The traveling \(k\)-median problem: approximating optimal network coverage ⋮ The online \(k\)-server problem with rejection ⋮ On randomization in on-line computation. ⋮ Delayed information and action in on-line algorithms ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ On online algorithms with advice for the \(k\)-server problem ⋮ On the power of randomization in on-line algorithms ⋮ Randomized competitive algorithms for the list update problem ⋮ Shortest paths without a map ⋮ On multi-threaded Paging
This page was built for publication: An optimal on-line algorithm for metrical task system
