Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
Capital Budgeting Problems: A parameterized point of view
OR 2014 (Springer Verlag, pp. 205-211)
Abstract
| A fundamental financial problem is budgeting. A firm is given a set of investments X over a number of time periods. Every investment has a return and for every time period a price. Further for every time period there is budget for this project. The task is to choose a portfolio X' from X such that for every time period the prices of the portfolio do not exceed the budged and the return of the portfolio is maximized. |
| Since the capital budgeting problem is computational intractable and is defined on inputs of various informations, we study the fixed-parameter tractability of the problem. The idea behind fixed-parameter tractability is to split the complexity into two parts - one part that depends purely on the size of the input, and one part that depends on some parameter of the problem that tends to be small in practice. We show that for the multi-period problem the number of investments and the sum of all budgets can be chosen as a parameter such that the problem is fixed parameter tractable. For the single-period problem additionally the threshold value of the return can be chosen as a parameter. Thus for a lot of small parameter values we obtain efficient solutions for the capital budgeting problem. We also consider the connection between these parameterized problems and approximation and pseudopolynomial algorithms. |