Report Number: CS-TR-75-518
Institution: Stanford University, Department of Computer Science
Title: Aggregation of inequalities in integer programming.
Author: Chvatal, Vaclav
Author: Hammer, Peter L.
Date: August 1975
Abstract: Given an m $\times$ n zero-one matrix $\underset\tilde\to A$ we ask whether there is a single linear inequality $\underset\tilde\to a \underset\tilde\to x \leq b$ whose zero-one solutions are precisely the zero-one solutions of $\underset\tilde\to A \underset\tilde\to x \leq e$. We develop an algorithm for answering this question in O(m$n^2$) steps and investigate other related problems. Our results may be interpreted in terms of graph theory and threshold logic.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/518/CS-TR-75-518.pdf