Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site faron.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math
Subject: Re: Is this solvable in polynomial time ?
Message-ID: <511@faron.UUCP>
Date: Sat, 22-Mar-86 16:15:48 EST
Article-I.D.: faron.511
Posted: Sat Mar 22 16:15:48 1986
Date-Received: Tue, 25-Mar-86 03:02:48 EST
References: <723@uwvax.UUCP>
Organization: The MITRE Coporation, Bedford, MA
Lines: 35

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