Abstract
The complete set partitioning (CSP) problem is a special case of the set partitioning problem where the coefficient matrix has 2m−1 columns, each column being a binary representation of a unique integer between 1 and 2m−1,m⩾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 complexityO(3m), wheren=2m−1 is the size of the problem space.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
A. V. Aho, J. E. Hopcroft and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley (1974).
R. Garfinkel and G. Nemhauser,The set partitioning problem: Set covering problem with equality constraints, Operations Research 17, no. 5 (1969), pp. 848–856.
E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press (1978).
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).
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.
C. H. Lin and H. M. Salkin,An efficient algorithm for the complete set partitioning problem. Discrete Applied Mathematics 6 (1983), pp. 149–156.
C. L. Liu,Introduction to Combinational Mathematics, Computer Science Press (1971).
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.
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).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yun Yeh, D. A dynamic programming approach to the complete set partitioning problem. BIT 26, 467–474 (1986). https://doi.org/10.1007/BF01935053
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01935053