[net.math] Is this solvable in polynomial time ?

medhi@uwvax.UUCP (Deep {ankar} Medhi) (03/21/86)

 Consider the following problem :

    find an x such that   A x <= b,

         where  A is an m x n matrix and b is an m-vector.
         ( Assume that rank of A is m )


 Is there a polynomial time algorithm to find x ( i.e, just finding a
 a feasible point ) ?  Or do you know of anybody working on this 
 problem ?


 Deepankar Medhi
 ARPA : medhi@rsch.wisc.edu
 UUCP : seismo!uwvax!medhi

bs@faron.UUCP (Robert D. Silverman) (03/23/86)

> 
>  Consider the following problem :
> 
>     find an x such that   A x <= b,
> 
>          where  A is an m x n matrix and b is an m-vector.
>          ( Assume that rank of A is m )
> 
> 
>  Is there a polynomial time algorithm to find x ( i.e, just finding a
>  a feasible point ) ?  Or do you know of anybody working on this 
>  problem ?
> 
> 
>  Deepankar Medhi
>  ARPA : medhi@rsch.wisc.edu
>  UUCP : seismo!uwvax!medhi

Have you been hiding under a rock?? Both Khachian's ellipsoidal algorithm
(discovered around 1978) and Karmarkar's algorithm (discovered about
2 years ago) solve the feasible point problem as well as the optimization
problem of linear programming in polynomial time. Khachian's algorithm is
impractical mainly due to two reasons:

(1) Numerical instability (I've seen matrices arise in the computations
with condition numbers in excess of 10^100 for even small (50 variable)
problems.)

(2) Degree of the polynomial. Depending on the individual variation it is
around N^6.

The jury is still out on Karmarkar's algorithm, including some very hot
debates. It however is an N^(3.5) algorithm in most variations.
 
Bob Silverman