neveu@lll-crg.ARPA (Charles Neveu) (12/20/84)
> ... > There has been a great deal of media "hype" on this algorithm, somewhat > similar to the hype which followed the Khatchian algorithm 4 years > ago, and which turned out to be highly exaggerated. The value of the > Karmaker algorithm remains to be seen. > ... > David G. Cantor What was the Khatchian algorithm? How was it hyped and what were its limitations? Charles Neveu
dgc@ucla-cs.UUCP (12/25/84)
[*** REPLACE THIS LINE WITH YOUR MESSAGE ***]
"What was the Khatchian algorithm? How was it hyped and what
were its limitations?"
The Karmaker algorithm was the first published "polynomial-time"
algorithm for linear programming. It appeared in the (very important)
Soviet Journal "Doklady" in 1979. It was written in Russian and was
not noticed in the western world until after its English translation
appeared, several months after original publication.
While the commonly used "simplex algorithm" is normally quite quick,
the only known proofs of convergence yield exponentially-large upper
bounds for computing time. The simplex algorithm works by traversing
the (finitely many) vertices of a high-dimensional polyhedra, going
from one vertex to an adjacent vertex, always uphill (i.e. always
increasing, well, at least not decreasing, the objective function). At
any particular vertex, there may be several adjacent vertices which are
"uphill". The simplex algorithm doesn't give a good rule for choosing
one, and so may be considered non-deterministic. Indeed, there exist
problems for which the simplex algorithm may take exponentially long
(if the "worst" uphill choice is made at each step). A simple example
of such a problem requires traversing all of the vertices of a slightly
distorted n-dimensional hypercube.
When Khatchian's algorithm was first noticed, lavish praise and claims
appeared in Science Magazine and numerous newspapers, including both
the New York Times and the Los Angeles Times. Symposia were held to
study it, etc. However, when implemented, it turned out to be very SLOW
compared with the standard simplex algorithm, and it has not replaced
that algorithm. Of course, from a theoretical point of view, the
discovery of this algorithm was quite exciting.
It is worth noting what "polynomial time" means, in this context. A
linear programming problem may be described as having, say, m variables
and n constraints. One might think that "polynomial time" would mean
that computing time (the time is roughly proportional to the number of
arithmetic operations) is bounded by a polynomial in m and n. This is
true for say, Gauss' algorithm for matrix inversion, where the number
of arithmetic operations to invert an n by n matrix is bounded by a
constant times n cubed. For the currently known linear programming
algorithms, this is not the case. What "polynomial time" means is
that computing time is bounded by a polynomial in the "length of the
input" (assuming a "reasonable" encoding of the input -- this is
extremely significant for "sparse" problems, where a problem with m and
n both very large can be encoded to have short input -- such encodings
are not allowed when estimating the time in either the Khatchian or
Karmaker algorithms). Thus, for fixed m and n, the time is bounded
by a polynomial in r, the number of binary bits required to express
the various coefficients. For such problems the amount of work could
increase as more and more accuracy is prescribed.
David G. Cantor
ARPA: dgc@ucla-locus.arpa
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgcdgc@ucla-cs.UUCP (12/25/84)
[*** REPLACE THIS LINE WITH YOUR MESSAGE ***]
I inavdertently typed "Karmaker" in the first line of my posting
concerning the Katchian algorithm. The first paragraph should read:
The Khatchain algorithm was the first published "polynomial-time"
algorithm for linear programming. It appeared in the (very important)
Soviet Journal "Doklady" in 1979. It was written in Russian and was
not noticed in the western world until after its English translation
appeared, several months after original publication.
David G. Cantor
ARPA: dgc@ucla-locus.arpa
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgc