Solving knapsack problems with S-curve return functions |
| |
Authors: | Semra A?ral? Joseph Geunes |
| |
Institution: | Department of Industrial and Systems Engineering, University of Florida, PO Box 116595, Gainesville, FL 32611, United States |
| |
Abstract: | 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. |
| |
Keywords: | Non-linear programming OR in strategic planning Dynamic programming Marketing |
本文献已被 ScienceDirect 等数据库收录! |
|