Capital Budgeting Problems: A Parameterized Point of View

A fundamental financial problem is budgeting. A firm is given a set of financial instruments $$X=\{x_1,\ldots ,x_n\}$$ X = { x 1 , … , x n } over a number of time periods T. Every instrument $$x_i$$ x i has a return of $$r_i$$ r i and for time period $$t=1,\ldots ,T$$ t = 1 , … , T a price of $$p_{t,i}$$ p t , i . Further for every time period t there is budget $$b_t$$ b t . The task is to choose a portfolio $$X'$$ X ′ from X such that for every time period $$t=1,\ldots ,T$$ t = 1 , … , T the prices of the portfolio do not exceed the budget $$b_t$$ b t and the return of the portfolio is maximized. We study the fixed-parameter tractability of the problem. For a lot of small parameter values we obtain efficient solutions for the capital budgeting problem. We also consider the connection to pseudo-polynomial algorithms.