# A fast algorithm for quadratic resource allocation problems with nested constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2020.

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

- [Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case](https://mlsanity.com/paper/2306.05865/) (2023)

## Abstract (arXiv)

We study the quadratic resource allocation problem and its variant with lower and upper constraints on nested sums of variables. This problem occurs in many applications, in particular battery scheduling within decentralized energy management (DEM) for smart grids. We present an algorithm for this problem that runs in O(n log n) time and, in contrast to existing algorithms for this problem, achieves this time complexity using relatively simple and easy-to-implement subroutines and data structures. This makes our algorithm very attractive for real-life adaptation and implementation. Numerical comparisons of our algorithm with a subroutine for battery scheduling within an existing tool for DEM research indicates that our algorithm significantly reduces the overall execution time of the DEM system, especially when the battery is expected to be completely full or empty multiple times in the optimal schedule. Moreover, computational experiments with synthetic data show that our algorithm outperforms the currently most efficient algorithm by more than one order of magnitude. In particular, our algorithm is able to solves all considered instances with up to one million variables in less than 17 seconds on a personal computer.