**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!dgc

**dgc@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