Discrete Effort Distribution via Regret-enabled Greedy Algorithm

Abstract

This paper addresses resource allocation problem with a separable objective function under a single linear constraint, formulated as maximizing ${\sum }_{j=1}^n{R}_j(x_j)$ subject to ${\sum }_{j=1}^n{x}_j=k$ and $x_j\in \{0,\dots ,m\}$. While classical dynamic programming approach solves this problem in $O(n^2{m}^2)$ time, we propose a regret-enabled greedy algorithm that achieves $O(n\log n)$ time when $m=O(1)$. The algorithm significantly outperforms traditional dynamic programming for small $m$. Our algorithm actually solves the problem for all $k(0\le k\le nm)$ in the mentioned time.