Chasing Convex Functions With Long-term Constraints
Adam Lechowicz, University of Massachusetts Amherst
We introduce and study a family of online metric problems with long-term constraints motivated by emerging applications in the design of sustainable systems. In these problems, a player makes sequential decisions represented as points in a metric space, with the goal of simultaneously minimizing a time-varying "hitting cost" and a switching cost determined by the metric. Over a given time horizon, the player's decisions must also satisfy a long-term demand constraint, where the fraction of demand satisfied at each step is described by a known affine function. Solutions to these types of problems find a wide array of applications, such as resource allocation in sustainable energy and computing systems. We design optimal algorithms for the case of hitting cost functions with bounded gradients and weighted L1 metrics. Given some additional "advice" (e.g., predictions from a machine learning model), we show a learning-augmented algorithm that significantly improves performance while retaining bounded worst-case guarantees. We evaluate our proposed algorithms in a set of numerical experiments.