Systems of linear inequalities

Click For Summary
SUMMARY

The discussion centers on the search for a polynomial time algorithm to solve systems of linear inequalities. The Simplex algorithm is noted for its exponential worst-case performance, while Karmarkar's algorithm offers a time complexity of O(n^3.5 * L^2) but is primarily designed for optimization rather than direct solution finding. Participants express a need for a more efficient algorithm that can determine the existence of solutions for such systems. The conversation highlights the limitations of existing methods and the ongoing quest for improved algorithms in this area.

PREREQUISITES
  • Understanding of linear programming concepts
  • Familiarity with the Simplex algorithm
  • Knowledge of Karmarkar's algorithm and its applications
  • Basic grasp of polynomial time complexity
NEXT STEPS
  • Research advancements in polynomial time algorithms for linear inequalities
  • Explore the theoretical foundations of Karmarkar's algorithm
  • Investigate alternative methods for solving linear inequalities
  • Study the implications of algorithmic complexity in optimization problems
USEFUL FOR

Mathematicians, computer scientists, and optimization specialists interested in algorithm development and efficiency in solving linear inequalities.

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:
Physics 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.
 

Similar threads

Undergrad A true or false statement concerning condition number of a matrix
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Want to understand how to express the derivative as a matrix
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Analogy question for algebraists
  • · Replies 1 ·
Replies
1
Views
2K
High School What unique contributions to math did linear algebra make?
  • · Replies 19 ·
Replies
19
Views
4K
Graduate How to solve a system of linear inequalities with absolute magnitudes?
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Proving inequality about dimension of quotient vector spaces
  • · Replies 25 ·
Replies
25
Views
4K
Can this system of inequalities be solved for x?
  • · Replies 5 ·
Replies
5
Views
2K
MHB Linear system of equations: Echelon form/Solutions
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Bohmian Prediction of Bell Inequality Violations
  • · Replies 45 ·
2
Replies
45
Views
5K
High School Can Linear Systems of Equations Have More Than Three Solutions?
  • · Replies 29 ·
Replies
29
Views
3K