Chasing Convex Functions with Long-term Constraints

Abstract

We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions ${\mathbf{x}}_t$ in a metric space $(X,d)$ to simultaneously minimize their hitting cost $f_t({\mathbf{x}}_t)$ and switching cost as determined by the metric. Over the time horizon $T$, the player must satisfy a long-term demand constraint ${\sum }_{t}c({\mathbf{x}}_t)\ge 1$, where $c({\mathbf{x}}_t)$ 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/computing systems. We devise optimal competitive and learning-augmented algorithms for the case of bounded hitting cost gradients and weighted ${\ell }_1$ metrics, and further show that our proposed algorithms perform well in numerical experiments.

Accepted to ICML 2024. 31 pages, 12 figures