OR 2015 (Springer Verlag, pp. 79-85)

Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld

Computing Partitions with Applications to Capital Budgeting Problems.
OR 2015 (Springer Verlag, pp. 79-85)

F. Gurski

J. Rethmann

E. Yilmaz

Abstract

We consider the following capital budgeting problem. A firm is given a set of investment opportunities X = {x₁,…,x_n} and a number m of portfolios. Every investment x_i, 1 ≤ i ≤ n, has a return of r_i and a price of p_i. Further for every portfolio j there is capacity c_j. The task is to choose m disjoint portfolios X'₁,…, X'_m from X such that for every 1 ≤ j ≤ m the prices in X'_j do not exceed the capacity c_j and the total return of this selection is maximized. From a computational point of view this problem is intractable, even for m=1 (see Kellerer, Pferschy, Pisinger: Knapsack Problems. Springer-Verlag, Berlin, 2010).

Since the problem is defined on inputs of various informations, in this paper we consider the fixed-parameter tractability for several parameterized versions of the problem. For a lot of small parameter values we obtain efficient solutions for the partitioning capital budgeting problem. We also consider the connection to pseudo-polynomial algorithms.