AN ALGORITHM FOR COMPUT IN3 THE ALFHA-WIDTH OF (0,1) MATRICES

from the United States Naval Postgraduate School A branch and bound technique is used to derive an algorithm for computing the alpha-width of any matrix of zeros and ones. Through computation of the 1-width of over 200 matrices of various dimensions, it is found that less than 20 minutes of computation time on the Control Data l60i; digital computer is required to complete the compu-tation for most matrices. Applications of the algorithm to integer programming and to various targeting problems are described. Exten-sions are suggested for computing the minimal cost alpha-width, and for computing a minimal C-cover