Accession Number : ADA018461
Title : Aggregation of Inequalities in Integer Programming.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Chvatal,Vaclav ; Hammer,Peter L.
Report Date : AUG 1975
Pagination or Media Count : 29
Abstract : Given an m x n zero-one matrix A approximately it is asked whether there is a single linear inequality ax less than or equal to b whose zero-one solutions are precisely the zero-one solutions of Ax less than or equal to e. An algorithm is developed for answering this question in O(mn sq) steps and other related problems are investigated. The results may be interpreted in terms of graph theory and threshold logic.
Descriptors : *Integer programming, *Inequalities, *Combinatorial analysis, Matrices(Mathematics), Mathematical logic, Graphics
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE