Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints

Abstract

We introduce and study spatiotemporal online allocation with deadline constraints ($\mathsf{SOAD}$), a new online problem motivated by emerging challenges in sustainability and energy. In $\mathsf{SOAD}$, an online player completes a workload by allocating and scheduling it on the points of a metric space $(X,d)$ while subject to a deadline $T$. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metric $d(\cdot ,\cdot )$ that captures, e.g., an overhead cost. $\mathsf{SOAD}$ formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for $\mathsf{SOAD}$ along with a matching lower bound establishing its optimality. Our main algorithm, \textsc{ST-CLIP}, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that \textsc{ST-CLIP} substantially improves on heuristic baseline methods.

Accepted to SIGMETRICS 2025. 49 pages, 21 figures

References in corpus (7)

• Carbon Explorer: A Holistic Approach for Designing Carbon Aware Datacenters
• Let's Wait Awhile: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud
• On the Limitations of Carbon-Aware Temporal and Spatial Workload Shifting in the Cloud
• The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
• The War of the Efficiencies: Understanding the Tension between Carbon and Energy Optimization
• LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand
• Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model