Chasing Convex Functions with Long-term Constraints
<|reference_start|>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 $\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/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.<|reference_end|>
@article{lechowicz2024chasing,
    title={Chasing Convex Functions with Long-term Constraints},
    author={Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad
  Hajiesmaili, Adam Wierman, Prashant Shenoy},
    journal={arXiv preprint arXiv:2402.14012},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.14012},
    primaryClass={cs.DS cs.LG}
}