On the k-server conjecture

DOI10.1145/195058.195245zbMath1345.68278OpenAlexW2031323309MaRDI QIDQ2817642

Elias Koutsoupias, Christos H. Papadimitriou

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Related Items (15)

A better lower bound on the competitive ratio of the randomized 2-server problem ⋮ On the competitive ratio of the work function algorithm for the \(k\)-server problem ⋮ The CNN problem and other \(k\)-server variants ⋮ A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem ⋮ The 2-evader problem ⋮ The orthogonal CNN problem ⋮ Distributed near-optimal matching ⋮ The \(k\)-server problem ⋮ Two online algorithms for the ambulance systems ⋮ The combinatorics of effective resistances and resistive inverses ⋮ Distributed near-optimal matching ⋮ Competitive analysis of randomized paging algorithms ⋮ The 3-server problem in the plane. ⋮ A randomized algorithm for two servers on the line. ⋮ The online \(k\)-server problem with max-distance objective

This page was built for publication: On the k-server conjecture