A dynamic programming approach to the complete set partitioning problem (Q1091142)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A dynamic programming approach to the complete set partitioning problem |
scientific article; zbMATH DE number 4009823
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A dynamic programming approach to the complete set partitioning problem |
scientific article; zbMATH DE number 4009823 |
Statements
A dynamic programming approach to the complete set partitioning problem (English)
0 references
1986
0 references
The complete set partitioning (CSP) problem is a special case of the set partitioning problem where the coefficient matrix has \(2^ m-1\) columns, each column being a binary representation of a unique integer between 1 and \(2^ m-1\), \(m\geq 1\). It has wide applications in the area of corporate tax structuring in operations research. In this paper we propose a dynamic programming approach to solve the CSP problem, which has time complexity \(O(3^ m)\), where \(n=2^ m-1\) is the size of the problem space.
0 references
integer programming
0 references
dynamic programming
0 references
analysis of algorithms
0 references
corporate tax structuring
0 references
