'Simple' Zero-One Problems: Set Covering, Matchings and Coverings in Graphs.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1971
- Accession Number
- AD0723578
Entities
People
- Manfred W. Padberg
Organizations
- Carnegie Mellon University