online-algorithms

The paper proves the k-server conjecture by demonstrating that the work function algorithm achieves a competitive ratio of k on every metric space.

This paper extends CONES to time-varying loss functions, showing bounds for regret and movement cost using projected proximal algorithms in convex optimization.

Proposes SOLAR, a learning-augmented framework for semantic cache replacement in LLM agents, outperforming classical heuristics by using regret-based modification timing and Bayesian online learning. Achieves constant competitive ratio and significant improvements over FIFO.