Journal
JOURNAL OF DISCRETE ALGORITHMS
Volume 34, Issue -, Pages 137-146Publisher
ELSEVIER
DOI: 10.1016/j.jda.2015.06.001
Keywords
Polynomial-time algorithms; Complexity analysis; Data structure; Nonlinear combinatorial optimization
Categories
Funding
- NSF [CMMI-1362619, CMMI-1451078]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available