-5
$\begingroup$

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?

$\endgroup$
8
  • 1
    $\begingroup$ In general (for arbitrary $A$), your problem is equivalent to linear programming. $\endgroup$ Jul 18, 2012 at 17:49
  • $\begingroup$ Yes, it seems so. But, I need something fast. $\endgroup$
    – Star
    Jul 18, 2012 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, 2012 at 19:57
  • 1
    $\begingroup$ @Gopi this IS linear programming, factorization won't help by itself. $\endgroup$ Jul 19, 2012 at 4:55
  • 1
    $\begingroup$ @Gopi you were this close to a strongly polynomial time algorithm for linear programming ;) $\endgroup$ Jul 19, 2012 at 15:29

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

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.