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