
Accession Number : AD0723578
Title : 'Simple' ZeroOne Problems: Set Covering, Matchings and Coverings in Graphs.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Padberg,Manfred W.
Report Date : APR 1971
Pagination or Media Count : 38
Abstract : Set covering problems are often referred to as 'simple' zeroone problems. The author proposes a definition of 'simplicity' of an arbitrary zeroone problem. It is shown that whenever a zeroone 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 edgematching and nodecovering problems defined in graphs. (Author)
Descriptors : (*LINEAR PROGRAMMING, GRAPHICS), CONVEX SETS, MATRICES(MATHEMATICS), THEOREMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE