TY - JOUR
T1 - A faster algorithm for the resource allocation problem with convex cost functions
AU - Shi, Cong
AU - Zhang, Huanan
AU - Qin, Chao
N1 - Funding Information:
The authors thank the Area Editor Professor Iain A. Stewart, and three anonymous referees for their constructive comments and suggestions, which helped to improve both the content and the exposition of this paper. The work is partially supported by NSF grants CMMI-1362619 and CMMI-1451078 .
Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/9/1
Y1 - 2015/9/1
N2 - We revisit the classical resource allocation problem with general convex objective functions, subject to an integer knapsack constraint. This class of problems is fundamental in discrete optimization and arises in a wide variety of applications. In this paper, we propose a novel polynomial-time divide-and-conquer algorithm (called the multi-phase algorithm) and prove that it has a computational complexity of O(nlog nlog N), which outperforms the best known polynomial-time algorithm with O(n(log N)2).
AB - We revisit the classical resource allocation problem with general convex objective functions, subject to an integer knapsack constraint. This class of problems is fundamental in discrete optimization and arises in a wide variety of applications. In this paper, we propose a novel polynomial-time divide-and-conquer algorithm (called the multi-phase algorithm) and prove that it has a computational complexity of O(nlog nlog N), which outperforms the best known polynomial-time algorithm with O(n(log N)2).
UR - http://www.scopus.com/inward/record.url?scp=84939574439&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84939574439&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2015.06.001
DO - 10.1016/j.jda.2015.06.001
M3 - Article
AN - SCOPUS:84939574439
SN - 1570-8667
VL - 34
SP - 137
EP - 146
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
ER -