Accession Number:

AD0723578

Title:

'Simple' Zero-One Problems: Set Covering, Matchings and Coverings in Graphs.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1971-04-01

Pagination or Media Count:

38.0

Abstract:

Set covering problems are often referred to as simple zero-one problems. The author proposes a definition of simplicity of an arbitrary zero-one problem. It is shown that whenever a zero-one problem is simple the convex hull of integer solutions to such a problem is easily obtainable. Using a recently proven property of the set covering problem, the author shows that this class of problems is structurally simple. This result is used to derive in explicit form the convex hull of integer solutions to the edge-matching and node-covering problems defined in graphs. Author

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE