Algorithm MinWtBasis for Simplifying Conjunctions of Monomial Inequalities
Christopher W. Brown · 2010
Abstract : This paper defines a new algorithm 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.