Solving knapsack problems with S-curve return functions Academic Article uri icon

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. 2007 Elsevier B.V. All rights reserved.

published proceedings

  • EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

author list (cited authors)

  • Agrali, S., & Geunes, J.

citation count

  • 15

complete list of authors

  • Ağralı, Semra||Geunes, Joseph

publication date

  • March 2009