3
$\begingroup$

I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution.

  1. What is the best worst case running time for this decision problem if it is considered as an LP?
  2. Is it possible to decide the feasibility using Gaussian elimination method or some other methods like this?

Note, however, that the entries of the matrix $A$ can be rational.

0 Answers 0