Chasing Convex Functions with Long-term Constraints
Adam Lechowicz Nicolas Christianson Bo Sun Noman Bashir Mohammad Hajiesmaili Adam Wierman Prashant Shenoy
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.