Industrial and Systems Engineering
University of Florida

EIN 6918: Graduate Seminar
Spring 2008

January 17, 2008

3PM, MAEB 211

Solving Knapsack Problems with S-Curve Return Functions

Semra Agrala

Department of Industrial and Systems Engineering

University of Florida

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.

This is a joint work with Dr. Joseph Geunes.