-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?

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

1 Answer 1

Reset to default
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 w−x+y−z=b into w+y−t=0 and t−x−z=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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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