Computing Partitions with Applications to Capital Budgeting Problems

We consider the following capital budgeting problem. A firm is given a set of investment opportunities \(X=\{x_1,\ldots ,x_n\}\) and a number m of portfolios. Every investment \(x_i\), \(1\le i\le 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'_1,\ldots , X'_m\) from X such that for every \(1\le j\le 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\) [8]. 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.