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

We introduce and study spatiotemporal online allocation with deadline constraints (𝖲𝖮𝖠𝖣), a new online problem motivated by emerging challenges in sustainability and energy. In 𝖲𝖮𝖠𝖣, 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(⋅, ⋅) that captures, e.g., an overhead cost. 𝖲𝖮𝖠𝖣 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 𝖲𝖮𝖠𝖣 along with a matching lower bound establishing its optimality. Our main algorithm, 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 ST-CLIP substantially improves on heuristic baseline methods.

Note

🚧 We are working on improving the comment and description quality of the code in this repository -- please check back in a few weeks for a more "user-friendly" codebase!

Python code

Our experimental code has been written in Python and Cython. We recommend using a tool to manage Python virtual environments, such as Miniconda. There are several required Python packages:

• Cython
• NumPy
• pandas
• SciPy
• tqdm for progress bars
• Matplotlib for creating plots
• Seaborn
• mat4py
• Python Optimal Transport

Files and Descriptions

(🚧 under construction)

Dataset References

Carbon Intensity Data:

Electricity Maps. retrieved 2024. https://www.electricitymaps.com

WattTime. retrieved 2024. https://watttime.org

Carbon Intensity Forecasts:

Diptyaroop Maji, Prashant Shenoy, and Ramesh K. Sitaraman. 2022. CarbonCast: multi-day forecasting of grid carbon intensity. In Proceedings of the 9th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys '22). Association for Computing Machinery, New York, NY, USA, 198–207. https://doi.org/10.1145/3563357.3564079

Reproducing Results

(🚧 under construction)

Citation

@inproceedings{lechowicz2025soad, title={Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints}, volume={9}, ISSN={2476-1249}, url={http://dx.doi.org/10.1145/3711701}, DOI={10.1145/3711701}, number={1}, journal={Proceedings of the ACM on Measurement and Analysis of Computing Systems}, publisher={Association for Computing Machinery (ACM)}, author={Lechowicz, Adam and Christianson, Nicolas and Sun, Bo and Bashir, Noman and Hajiesmaili, Mohammad and Wierman, Adam and Shenoy, Prashant}, year={2025}, month={Mar}, pages={1–49} }