Solving knapsack problems with S-curve return functions
- Additional Document Info
- View All
We consider the allocation of a limited budget to a set of activities or investments in order to maximize return from investment. In a number of practical contexts (e.g., advertising), the return from investment in an activity is effectively modeled using an S-curve, where increasing returns to scale exist at small investment levels, and decreasing returns to scale occur at high investment levels. We demonstrate that the resulting knapsack problem with S-curve return functions is NP-hard, provide a pseudo-polynomial time algorithm for the integer variable version of the problem, and develop efficient solution methods for special cases of the problem. We also discuss a fully-polynomial-time approximation algorithm for the integer variable version of the problem. 2007 Elsevier B.V. All rights reserved.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
author list (cited authors)
complete list of authors
Ağralı, Semra||Geunes, Joseph