.png){kind=icon}
.png){kind=icon}
Return
Discrete Effort Distribution via Regret-Enabled Greedy Algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses resource allocation problem with a separable objective function under a single linear constraint, formulated as maximizing Sigma(n) (j=1) R-j(x(j)) subject to Sigma(n) (j=1) x(j) = k and x(j) is an element of {0,..., 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 <= k <= nm) in the mentioned time.
Keywords:
Regret-enabled Greedy Algorithm
Discrete Effort Distribution
Resource Allocation
(max, plus ) convolution
Heaps
Journal
C
IF:
0
Papers:
24
Citations:
0