Set Partitioning and Chain Decomposition
There is given a finite set I and a family of subsets of I. We consider the problem of determining a minimum cardinality subfamily that is a partition of I. A branch-and-bound algorithm is presented. The bounds are obtained by determining chain decompositions of directed acyclic graphs. The computation time required to determine a bound is bounded by a polynomial in the cardinality of I. Some computational experience is reported and relationships with other methods are discussed.
Year of publication: |
1974
|
---|---|
Authors: | Nemhauser, G. L. ; L. E. Trotter, Jr. ; Nauss, R. M. |
Published in: |
Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 20.1974, 11, p. 1413-1423
|
Publisher: |
Institute for Operations Research and the Management Sciences - INFORMS |
Saved in:
Saved in favorites
Similar items by person
-
Set partitioning and chain decomposition
Nemhauser, G. L., (1974)
-
The asymmetric traveling salesman problem with replenishment arcs
Boland, N. L., (2000)
-
Optimal Political Districting by Implicit Enumeration Techniques
Garfinkel, R. S., (1970)
- More ...