Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2503.11107 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914028331204608 |
|---|---|
| author | Cao, Song Zhu, Taikun Jin, Kai |
| author_facet | Cao, Song Zhu, Taikun Jin, Kai |
| contents | 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^2m^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\leq k\leq nm)$ in the mentioned time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_11107 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrete Effort Distribution via Regret-enabled Greedy Algorithm Cao, Song Zhu, Taikun Jin, Kai Data Structures and Algorithms 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^2m^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\leq k\leq nm)$ in the mentioned time. |
| title | Discrete Effort Distribution via Regret-enabled Greedy Algorithm |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.11107 |