Online \(k\)-taxi via double coverage and time-reverse primal-dual

DOI10.1007/978-3-030-73879-2_2zbMath1482.90177arXiv2012.02226OpenAlexW3162890406MaRDI QIDQ5918418

Christian Coester, Niv Buchbinder, Joseph (Seffi) Naor

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

online algorithms\(k\)-serverdual fitting\(k\)-taxi

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (1)

Approximation algorithms for clustering with dynamic points

Cites Work

• Unnamed Item
• Unnamed Item
• The \(k\)-server problem
• On the power of randomization in on-line algorithms
• Competitive \(k\)-server algorithms
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Competitive paging algorithms
• On the k -server conjecture
• The online 𝑘-taxi problem
• k-server via multiscale entropic regularization
• k-Servers with a Smile: Online Algorithms via Projections
• Approximating Sparse Covering Integer Programs Online
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Online \(k\)-taxi via double coverage and time-reverse primal-dual