Computing Partitions with Applications to Capital Budgeting Problems

Frank Gurski (), Jochen Rethmann () and Eda Yilmaz ()
Additional contact information
Frank Gurski: University of Düsseldorf
Jochen Rethmann: Niederrhein University of Applied Sciences
Eda Yilmaz: University of Düsseldorf

A chapter in Operations Research Proceedings 2015, 2017, pp 79-85 from Springer

Abstract: Abstract 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.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-42902-1_11

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_11

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().