A dynamic programming approach to the complete set partitioning problem (Q1091142)

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.