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. a) How feasibility of this system can be checked without using linear programming? b) Is the ellipsoid method useful for checking feasibility of the corresponding polyhedral?

  • 1
    $\begingroup$ In general (for arbitrary $A$), your problem is equivalent to linear programming. $\endgroup$ – Mahdi Cheraghchi Jul 18 '12 at 17:49
  • $\begingroup$ Yes, it seems so. But, I need something fast. $\endgroup$ – Star Jul 18 '12 at 17:57
  • 1
    $\begingroup$ This forum is dedicated to Theoretical Computer Science question. Maybe you should try asking your question on Computer Science where it may be more welcolmed by the community? $\endgroup$ – Gopi Jul 18 '12 at 19:57
  • 1
    $\begingroup$ @Gopi this IS linear programming, factorization won't help by itself. $\endgroup$ – Sasho Nikolov Jul 19 '12 at 4:55
  • 1
    $\begingroup$ @Gopi you were this close to a strongly polynomial time algorithm for linear programming ;) $\endgroup$ – Sasho Nikolov Jul 19 '12 at 15:29

How can this system be solved without using linear programming?

It cannot.

Your problem is the linear feasibility problem in the standard form, with an extra condition that the constraint matrix is sparse. Now note:

(1) It is well-known that linear programming is equivalent to the linear feasibility problem in the standard form.

(2) You can easily convert a linear feasibility problem in the standard form to one with the extra condition that each row of the constraint matrix has at most three nonzero elements. For example, decompose wx+yz=b into w+yt=0 and txz=b, where t is a fresh nonnegative variable. (The detail is left as an exercise.)

These together mean that an algorithm for your problem can be used to solve the linear programming. Equivalently, you cannot hope for an essentially simpler algorithm for your problem than an algorithm for linear programming.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.