Triangularization: A Two-Processor Scheduling Problem.
Abstract
We explore the following matrix problem: Given an n x n boolean matrix, is there a permutation of the rows and a permutation of the columns such that the resulting matrix is lower triangular? We show the relationship of this matrix problem to the two important scheduling problems: optimization of code for pipelined execution and microcode compaction for very long instruction computers. This matrix problem is unclassified-it is unknown whether it is NP-Complete or whether it can be solved by a polynomial time algorithm. We find several minor extensions that would make the problem NP-Complete. Also, we show polynomial algorithms for a number of special cases of the problem, and develop a number of interesting techniques in the process. We also explore approximation algorithms and lower bounds.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1990
- Accession Number
- ADA326053
Entities
People
- Ramsey W. Haddad
Organizations
- Stanford University