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\}$$ X = { x 1 , … , x n } and a number m of portfolios. Every investment $$x_i$$ x i , $$1\le i\le n$$ 1 ≤ i ≤ n , has a return of $$r_i$$ r i and a price of $$p_{i}$$ p i . Further for every portfolio j there is capacity $$c_j$$ c j . The task is to choose m disjoint portfolios $$X'_1,\ldots , X'_m$$ X 1 ′ , … , X m ′ from X such that for every $$1\le j\le m$$ 1 ≤ j ≤ m the prices in $$X'_j$$ X j ′ do not exceed the capacity $$c_j$$ 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$$ 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.