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