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) \geq 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 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.