DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Triangularization: A Two-Processor Scheduling Problem.
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
APPROVED FOR PUBLIC RELEASE