🚀 go-pugleaf

In article <3677F039.5132@mcimail.com>,
Arthur L. Rubin <216-5888@mcimail.com> wrote:
>Dima Pasechnik wrote:

>> Ronald Hui <ronhui@hkpc.org> writes:

>> > If I have a linear inequality system for a set of variables xi, how can
>> > I find one solution that can satisfy the linear inequality constraint?

>> > I think linear programming is a possible method. But is there any faster
>> > and easier method?
>> In general, nothing faster is known.

>> Dmitrii

>I think the ellipsoid method has been shown to be faster than the
>simplex
>method is guaranteed to be, but, in practice, the simplex method is
>actually
>the fastest method.  (These are both linear programming methods, but I
>assume
>Mr. Hui was using "linear programming" to denote the simplex method.)

The speed of the ellipsoid method is not known practically; the 
bounds depend essentially on the size of the numbers as integers.
While it may be polynomial time in the sum of the absolute values
of the coefficients, this does not make the bound good.

However, the Karmarkar algorithm is generally faster for large problems.
Its speed comes from going into the solution set, and not along edges.
-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558