On Defining Sets of Vertices of the Hypercube by Linear Inequalities.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
The paper shows that for any subset S of vertices of the n-dimensional hypercube, indS or 2 supn-1, where indS is the minimum number of linear inequalities needed to define S. Furthermore, for any k in the range 1 or k or 2 supn-1, there is an S with indS 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
- Operations Research