Solving knapsack problems with S-curve return functions
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.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Paul H. Zipkin, 1980. "Simple Ranking Methods for Allocation of One Resource," Management Science, INFORMS, vol. 26(1), pages 34-43, January.
- Duncan M. Holthausen, Jr. & Gert Assmus, 1982. "Advertising Budget Allocation under Uncertainty," Management Science, INFORMS, vol. 28(5), pages 487-499, May.
- Ginsberg, William, 1974. "The multiplant firm with increasing returns to scale," Journal of Economic Theory, Elsevier, vol. 9(3), pages 283-292, November.
- Andris A. Zoltners & Prabhakant Sinha & Philip S. C. Chong, 1979. "An Optimal Algorithm for Sales Representative Time Management," Management Science, INFORMS, vol. 25(12), pages 1197-1207, December.
- Bretthauer, Kurt M. & Shetty, Bala, 2002. "The nonlinear knapsack problem - algorithms and applications," European Journal of Operational Research, Elsevier, vol. 138(3), pages 459-472, May.
- Gabriel R. Bitran & Arnoldo C. Hax, 1981. "Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables," Management Science, INFORMS, vol. 27(4), pages 431-441, April.
- Leonard M. Lodish, 1971. "Callplan: An Interactive Salesman's Call Planning System," Management Science, INFORMS, vol. 18(4-Part-II), pages 25-40, December.
- Thomas L. Morin & Roy E. Marsten, 1976. "An Algorithm for Nonlinear Knapsack Problems," Management Science, INFORMS, vol. 22(10), pages 1147-1158, June.
- Andris A. Zoltners & Prabhakant Sinha, 1980. "Integer Programming Models for Sales Resource Allocation," Management Science, INFORMS, vol. 26(3), pages 242-260, March.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:193:y:2009:i:2:p:605-615. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu)
If references are entirely missing, you can add them using this form.