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.