期刊
JOURNAL OF DISCRETE ALGORITHMS
卷 34, 期 -, 页码 137-146出版社
ELSEVIER
DOI: 10.1016/j.jda.2015.06.001
关键词
Polynomial-time algorithms; Complexity analysis; Data structure; Nonlinear combinatorial optimization
资金
- NSF [CMMI-1362619, CMMI-1451078]
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(n log n log N), which outperforms the best known polynomial-time algorithm with O(n( log N)(2)). (C) 2015 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据