Skip to main content
Top

2016 | OriginalPaper | Chapter

Capital Budgeting Problems: A Parameterized Point of View

Authors : Frank Gurski, Jochen Rethmann, Eda Yilmaz

Published in: Operations Research Proceedings 2014

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A fundamental financial problem is budgeting. A firm is given a set of financial instruments \(X=\{x_1,\ldots ,x_n\}\) over a number of time periods T. Every instrument \(x_i\) has a return of \(r_i\) and for time period \(t=1,\ldots ,T\) a price of \(p_{t,i}\). Further for every time period t there is budget \(b_t\). The task is to choose a portfolio \(X'\) from X such that for every time period \(t=1,\ldots ,T\) the prices of the portfolio do not exceed the budget \(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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)CrossRef Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)CrossRef
2.
go back to reference Cai, L., Chen, J.: On fixed-parameter tractability and approximability of np optimization problems. J. Comput. Syst. Sci. 54, 465–474 (1997)CrossRef Cai, L., Chen, J.: On fixed-parameter tractability and approximability of np optimization problems. J. Comput. Syst. Sci. 54, 465–474 (1997)CrossRef
3.
go back to reference Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, New York (2013)CrossRef Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, New York (2013)CrossRef
4.
go back to reference Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006) Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
5.
go back to reference Hromkovic, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Berlin (2004)CrossRef Hromkovic, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Berlin (2004)CrossRef
6.
go back to reference Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)CrossRef Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)CrossRef
7.
go back to reference Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2010) Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2010)
8.
go back to reference Šedová, J., Šeda, M.: A comparison of exact and heuristic approaches to capital budgeting. In: Proceedings of World Congress on Science, Engineering and Technology WCSET 2008, vol. 35, pp. 187–191 (2008) Šedová, J., Šeda, M.: A comparison of exact and heuristic approaches to capital budgeting. In: Proceedings of World Congress on Science, Engineering and Technology WCSET 2008, vol. 35, pp. 187–191 (2008)
9.
go back to reference Weingartner, H.M.: Capital budgeting of interrelated projects: survey and synthesis. Manage. Sci. 12(7), 485–516 (1966)CrossRef Weingartner, H.M.: Capital budgeting of interrelated projects: survey and synthesis. Manage. Sci. 12(7), 485–516 (1966)CrossRef
10.
go back to reference Weingartner, H.M., Ness, D.N.: Methods for the solution of the multidimensional 0/1 knapsack problem. Oper. Res. 15(1), 83–103 (1967)CrossRef Weingartner, H.M., Ness, D.N.: Methods for the solution of the multidimensional 0/1 knapsack problem. Oper. Res. 15(1), 83–103 (1967)CrossRef
Metadata
Title
Capital Budgeting Problems: A Parameterized Point of View
Authors
Frank Gurski
Jochen Rethmann
Eda Yilmaz
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-28697-6_29