A dynamic programming approach to the complete set partitioning problem. (English) Zbl 0622.68047
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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C10 | Integer programming |
| 90C39 | Dynamic programming |
| 05A05 | Permutations, words, matrices |
Keywords:
integer programming; dynamic programming; analysis of algorithms; corporate tax structuringReferences:
| [1] | A. V. Aho, J. E. Hopcroft and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley (1974). · Zbl 0326.68005 |
| [2] | R. Garfinkel and G. Nemhauser,The set partitioning problem: Set covering problem with equality constraints, Operations Research 17, no. 5 (1969), pp. 848–856. · Zbl 0184.23101 · doi:10.1287/opre.17.5.848 |
| [3] | E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press (1978). · Zbl 0442.68022 |
| [4] | C. H. Lin,Corporate Tax Structures and a Special Class of Set Partitioning Problems, Ph. D. Thesis, Department of Operation Research, Case Western Reserve University, Cleveland, OH (1976). |
| [5] | C. H. Lin and H. M. Salkin,Aggregation of subsidiary firms for minimal unemployment compensation payments via integer programming, Management Science 25, no. 4 (1979), pp. 405–408. · doi:10.1287/mnsc.25.12.1258 |
| [6] | C. H. Lin and H. M. Salkin,An efficient algorithm for the complete set partitioning problem. Discrete Applied Mathematics 6 (1983), pp. 149–156. · Zbl 0523.90062 · doi:10.1016/0166-218X(83)90069-0 |
| [7] | C. L. Liu,Introduction to Combinational Mathematics, Computer Science Press (1971). |
| [8] | J. Pierce,Application of combinatorial programming to a class of all zero-one integer programming problems, Management Science 15, no. 1 (1968), pp. 191–209. · doi:10.1287/mnsc.15.3.191 |
| [9] | H. M. Salkin, B. V. Dean, S. Morito, and C. H. Lin,On minimizing workman’s compensation payments by linear programming, in H. Salkin and J. Saha, eds,Studies in Linear Programming, North-Holland (1975). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
