| 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. |