Algorithm MinWtBasis for Simplifying Conjunctions of Monomial Inequalities

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 28, 2010
Accession Number
ADA526542

Entities

People

  • Christopher W. Brown

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Contrast
  • Equations
  • Inequalities
  • Information Operations
  • New York
  • Polynomials
  • United States
  • United States Naval Academy

Readers

  • Calculus or Mathematical Analysis
  • Operations Research