Deterministic 3-server on a circle and the limitation of canonical potentials

DOI10.1016/J.TCS.2024.114844MaRDI QIDQ6634376zbMATH OpenFDO

Authors Zhiyi Huang, Hanwen Zhang

Publication date 7 November 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114844

zbMATH Keywords

\(k\)-serveronline algorithmwork function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• \(k\)-server via multiscale entropic regularization
• \(k\)-servers with a smile: online algorithms via projections
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• A primal-dual randomized algorithm for weighted paging
• A tight bound on approximating arbitrary metrics by tree metrics
• An Optimal On-Line Algorithm for K Servers on Trees
• An optimal on-line algorithm for metrical task system
• Chasing Convex Bodies Optimally
• Chasing Convex Bodies with Linear Competitive Ratio
• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• New Ressults on Server Problems
• On the k -server conjecture
• On the competitive ratio of the work function algorithm for the k-server problem
• The 3-server problem in the plane.
• The \(k\)-server problem
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• The Randomized k-Server Conjecture is False!

Cited in

(1)

• Time-optimal k-server

This page was built for publication: Deterministic 3-server on a circle and the limitation of canonical potentials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6634376)