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

arXiv: https://arxiv.org/abs/2408.07831 · HTML: https://mlsanity.com/paper/2408.07831/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 83 references that are in the map.
- First posted on arXiv 14 Aug 2024.

## Builds on (most cited first, 28 of 28)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Carbon Explorer: A Holistic Approach for Designing Carbon Aware Datacenters](https://mlsanity.com/paper/2201.10036/) (2022)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging](https://mlsanity.com/paper/2010.00412/) (2020)
- [Let's Wait Awhile: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud](https://mlsanity.com/paper/2110.13234/) (2021)
- [Enabling Sustainable Clouds: The Case for Virtualizing the Energy System](https://mlsanity.com/paper/2106.08872/) (2021)
- [Metrical task systems on trees via mirror descent and unfair gluing](https://mlsanity.com/paper/1807.04404/) (2018)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting](https://mlsanity.com/paper/2303.17551/) (2023)
- [Optimal Posted Prices for Online Cloud Resource Allocation](https://mlsanity.com/paper/1704.05511/) (2017)
- [The Randomized k-Server Conjecture is False!](https://mlsanity.com/paper/2211.05753/) (2022)
- [On the Limitations of Carbon-Aware Temporal and Spatial Workload Shifting in the Cloud](https://mlsanity.com/paper/2306.06502/) (2023)
- [Pure entropic regularization for metrical task systems](https://mlsanity.com/paper/1906.04270/) (2019)
- [The War of the Efficiencies: Understanding the Tension between Carbon and Energy Optimization](https://mlsanity.com/paper/2306.16948/) (2023)
- [The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems](https://mlsanity.com/paper/1907.08735/) (2019)
- [LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demand](https://mlsanity.com/paper/2404.15211/) (2024)

## Built on by (most cited first, 1 of 1)

- [Dissecting the Carbon-SLO Tension in Geo-Distributed LLM Serving](https://mlsanity.com/paper/2610.14571/) (2026)

## Abstract (arXiv)

We introduce and study spatiotemporal online allocation with deadline constraints (mathsfSOAD), a new online problem motivated by emerging challenges in sustainability and energy. In mathsfSOAD, 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. mathsfSOAD 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 mathsfSOAD along with a matching lower bound establishing its optimality. Our main algorithm, textscST-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 textscST-CLIP substantially improves on heuristic baseline methods.