AN ALGORITHM FOR COMPUTING THE ALPHA-WIDTH OF (0,1) MATRICES.

Abstract

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 1604 digital computer is required to complete the computation for most matrices. Applications of the algorithm to integer programming and to various targeting problems are described. Extensions are suggested for computing the minimal cost alpha-width, and for computing a minimal C-cover. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1965
Accession Number
AD0475273

Entities

People

  • Walter L. Stanley

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Digital Computers
  • Heuristic Methods
  • Integer Programming
  • Mathematical Analysis
  • Mathematics
  • Targeting

Readers

  • International Relations, focusing on Korea-Africa and North Korea-South Korea relations, and Nigeria-Latin American Relations.
  • Linear Algebra
  • Operations Research