Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Systems of linear inequalities

  1. Apr 30, 2008 #1
    Is there a polynomial time algorithm (polynomial time in terms of the number of input constraints and variables) to solve a system of linear inequalities or or indicate whether a solution for a system of linear inequalities exists or not?
    Last edited: Apr 30, 2008
  2. jcsd
  3. Apr 30, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Polynomial time Simplex?
  4. Apr 30, 2008 #3
    Simplex is exponential in the worst-case. Although there's Karmarkar's algorithm, it is for optimization of an objective function. Although it can be used for solving systems of linear inequalities, it takes n^3.5*L^2 time. I was wondering if there was a faster algorithm for giving a solution to the systems of linear inequalities.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook