Details

Title:Algorithm MinWtBasis for simplifying conjunctions of monomial inequalities
Authors:Brown, Christopher W.
Serial Number:2010-01
Publication Date:1-28-2010
Abstract:This paper defines a new algorithm "MinWtBasis" which simplifies conjunctions of monomial inequalities. The simplified equivalent formula produced by MinWtBasis minimizes the sum over all inequalities in the conjunction of the number of non-strict variables appearing, and it runs in polynomial time. For strictly non-strict conjunctions of inequalities, this shows that the problem of finding a simplest equivalent formula is in P. This contrasts with the general case and the strict inequality case, in which finding the simplest equivalent formula is NP-Hard.
View ReportView bibtex