The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem

DOI10.1137/120885309zbMath1310.68255arXiv1110.6600OpenAlexW2061319653MaRDI QIDQ5419031

R. A. Sitters

Publication date: 4 June 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.6600

zbMATH Keywords

competitive analysisonline algorithms\(k\)-server problemwork function algorithmCNN problemmetrical service system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Queues and service in operations research (90B22) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Lipschitz selectors may not yield competitive algorithms for convex body chasing ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ Nested convex bodies are chaseable ⋮ Metrical service systems with multiple servers ⋮ Better Bounds for Online Line Chasing ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics

This page was built for publication: The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem