Algorithms for a Set Partitioning Problem Arising in the Design of Multipurpose Units
- 1 April 1977
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-26 (4) , 321-328
- https://doi.org/10.1109/tc.1977.1674841
Abstract
We consider an abstract partitioning problem which has applications to the design of standard libraries of multipurpose units (such as multi-purpose circuit cards) and to storage allocation in the presence of users with conflicting demands. Although the general problem of finding minimum cost partitions appears to be very difficult, we describe a dynamic programming approach which can be quite efficient if the parameters for the items to be partitioned take on only a limited number of distinct values.Keywords
This publication has 3 references indexed in Scilit:
- Worst-Case Analysis of a Placement Algorithm Related to Storage AllocationSIAM Journal on Computing, 1975
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974
- Worst-case analysis of memory allocation algorithmsPublished by Association for Computing Machinery (ACM) ,1972