Accession Number:

AD0775594

Title:

Two Computationally Difficult Set Covering Problems that Arise in Computing the 1-Width of Incidence Matrices of Steiner Triple Systems

Descriptive Note:

Technical summary rept.

Corporate Author:

WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER

Report Date:

1974-02-01

Pagination or Media Count:

16.0

Abstract:

Two minimum cardinality set covering problems of similar structure are presented as difficult test problems for evaluating the computational efficiency of integer programming and set covering algorithms. The smaller problem has 117 constraints and 27 variables and the larger one, constructed by H.J. Ryser, has 330 constraints and 45 variables. The constraint matrices of the two set covering problems are incidence matrices of Steiner triple systems. An optimal solution to the problem that the authors were able to solve the smaller one gives some new information on the 1-widths of members of this class of 0,1-matrices.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE