Solving knapsack problems with S-curve return functions Academic Article

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.

authors

• Geunes, Joseph

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

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

keywords

• Dynamic Programming
• Marketing
• Non-linear Programming
• Or In Strategic Planning

Digital Object Identifier (DOI)

• 10.1016/j.ejor.2007.10.060

start page

• 605

end page

• 615

volume

• 193

issue

• 2

URL

• http://dx.doi.org/10.1016/j.ejor.2007.10.060