Open Access. Powered by Scholars. Published by Universities.®
- Keyword
Articles 1 - 2 of 2
Full-Text Articles in Theory and Algorithms
Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer
Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer
Mathematical Sciences Technical Reports (MSTR)
This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …
Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski
Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski
Dartmouth Scholarship
This paper presents asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on the Parallel Disk Model proposed by Vitter and Shriver. A BMMC permutation maps a source index to a target index by an affine transformation over GF(2), where the source and target indices are treated as bit vectors. The class of BMMC permutations includes many common permutations, such as matrix transposition (when dimensions are powers of 2), bit-reversal permutations, vector-reversal permutations, hypercube permutations, matrix reblocking, Gray-code permutations, and inverse Gray-code permutations. The upper bound improves upon the asymptotic …