Accession Number : AD0781269
Title : On Defining Sets of Vertices of the Hypercube by Linear Inequalities.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Jeroslow,R. G.
Report Date : APR 1974
Pagination or Media Count : 13
Abstract : The paper shows that for any subset S of vertices of the n-dimensional hypercube, ind(S) < or + 2 sup(n-1), where ind(S) is the minimum number of linear inequalities needed to define S. Furthermore, for any k in the range 1 < or = k < or = 2 sup(n-1), there is an S with ind(S) = k, with the defining inequalities taken as canonical cuts. Other related results are included and all are proven by explicit constructions of the sets S or explicit definitions of such sets by linear inequalities. The paper is aimed at researchers in bivalent programming, since it provides upper bounds on the performance of algorithms which combine several linear constraints into one, even when the given constraints have a particularly simple form. (Author)
Descriptors : *Mathematical programming, *Inequalities, Convex sets, Theorems
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE