A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables per Inequality.

Abstract

We present a constructive algorithm for solving systems of linear inequalities (LI) with at most two variables per inequality. The algorithm is polynomial in the size of the input. The LI problem is of importance in complexity theory since it is polynomial time equivalent to linear programming. The subclass of LI treated in this paper is also of practical interest in mechanical verification systems, and we believe that the ideas presented can be extended to the general LI problem. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1979
Accession Number
ADA068228

Entities

People

  • Bengt Aspvall
  • Yossi Shiloach

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Inequalities
  • Linear Programming
  • Mathematics
  • Polynomials
  • Simplex Method
  • Verification

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Mathematical Modeling and Probability Theory.
  • Military Engineering.