Chasing Convex Functions with Long-term Constraints

We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions xₜ in a metric space $(X,d)$ to simultaneously minimize their hitting cost fₜ(xₜ) and switching cost as determined by the metric. Over the time horizon T, the player must satisfy a long-term demand constraint ∑ₜ c(xₜ) ≥ 1, where c(xₜ) denotes the fraction of demand satisfied at time t. Such problems can find a wide array of applications to online resource allocation in sustainable energy and computing systems. We devise optimal competitive and learning-augmented algorithms for specific instantiations of these problems, and further show that our proposed algorithms perform well in numerical experiments.