Competitive Algorithms for Generalized k -Server in Uniform Metrics

DOI10.1145/3568677OpenAlexW2735399061MaRDI QIDQ6075743

Grigorios Koumoutsos, Jesper Nederlof, Nikhil Bansal, Marek Eliáš

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3568677

zbMATH Keywords

competitive analysisonline algorithms\(k\)-server problem

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• A strongly competitive randomized paging algorithm
• Competitive algorithms for the weighted server problem
• The 2-evader problem
• Competitive analysis of randomized paging algorithms
• The CNN problem and other \(k\)-server variants
• Computing the chromatic number using graph decompositions via matrix rank
• The orthogonal CNN problem
• On the size of Kakeya sets in finite fields
• On the Continuous CNN Problem
• Extremal Combinatorics
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• Randomized Memoryless Algorithms for the Weighted and the Generalized k -server Problems
• Competitive algorithms for server problems
• The generalized two-server problem
• Competitive paging algorithms
• An optimal on-line algorithm for metrical task system
• On the k -server conjecture
• k-server via multiscale entropic regularization
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• The Randomized Competitive Ratio of Weighted k-Server Is at Least Exponential

This page was built for publication: Competitive Algorithms for Generalized k -Server in Uniform Metrics