Systems of linear inequalities

AI Thread 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 'Trigonometry problem of interest'

Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
View full post »

Thread 'Six Pencil Puzzle'

Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top