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

Abstract

Two minimum cardinality set covering 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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1973
Accession Number
AD0770853

Entities

People

  • D. R. Fulkerson
  • G. L. Nemhouser
  • L. E. Trotter Jr.

Organizations

  • Cornell University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Programming
  • Computers
  • Contractors
  • Contracts
  • Coverings
  • Efficiency
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • New York
  • Operations Research
  • Security
  • Systems Engineering

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Modeling and Simulation
  • Operations Research