Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following system of inequalities:

$$Ax=b \\ x\geq 0$$

$A$ is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational.

  1. How feasibility of this system can be checked without using linear programming?

  2. Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?

share|improve this question
I would guess that finding feasible points to this system is almost equivalent to LP. The ellipsoid method is not considered to be effective practically. Primal-dual interior methods are (but also, simplex is still pretty good). –  copper.hat Jul 19 '12 at 16:03
The question is whether feasibility of this polyhedral can be checked using ellipsoid method. Since in my problem entries are partly rational. If yes, what is the running time. I need it for theoretical part not practical side. –  Star Jul 19 '12 at 16:13
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.