Systems of linear inequalities

  • Thread starter sid_galt
  • Start date
  • #1
502
0

Main Question or Discussion Point

Hi,
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?
Thanks
 
Last edited:

Answers and Replies

  • #2
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
Polynomial time Simplex?
 
  • #3
502
0
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.
 

Related Threads for: Systems of linear inequalities

  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
979
  • Last Post
Replies
1
Views
999
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
463
Top