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