Systems of linear inequalities

Click For Summary
There is no known polynomial time algorithm specifically for solving systems of linear inequalities that is efficient in terms of the number of input constraints and variables. The Simplex algorithm, while commonly used, has exponential worst-case performance. Karmarkar's algorithm can solve these systems but operates at a complexity of n^3.5*L^2, which is not polynomial time. The discussion highlights the search for faster algorithms to determine the existence of solutions for such systems. Overall, the quest for a more efficient solution remains an open question in computational mathematics.
sid_galt
Messages
502
Reaction score
1
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:
Mathematics news on Phys.org
Polynomial time Simplex?
 
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Undergrad What Are the Benefits of Triangle Inequality in Mathematics?
  • · Replies 2 ·
Replies
2
Views
2K
MHB How to Graph a System of Inequalities for Investment Allocation?
  • · Replies 16 ·
Replies
16
Views
2K
High School Problem with simple inequality
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Relevant Literature for Noisy Linear Dynamical Systems
  • · Replies 1 ·
Replies
1
Views
2K
MHB What Are the Solutions to the System of Inequalities for Target Heart Rate?
  • · Replies 3 ·
Replies
3
Views
1K
MHB Solving system of linear inequalities
  • · Replies 9 ·
Replies
9
Views
3K
High School What do we mean when we say that x∈R
  • · Replies 21 ·
Replies
21
Views
6K
MHB Which Quadrant Contains No Solutions to This System of Inequalities?
  • · Replies 2 ·
Replies
2
Views
3K
Can this system of inequalities be solved for x?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Bohmian Prediction of Bell Inequality Violations
  • · Replies 45 ·
2
Replies
45
Views
5K