drick@hplvle.UUCP (drick) (01/03/85)
[bug food] Karmarkar's paper has not been published yet. Our facility librarian was able to get me a copy of it by calling Bell Labs. Whoever she talked to also sent along a four page monograph (author unknown) which answers the question: "Why is the new algorithm better than the simplex method and the ellipsoid method?" A couple of interesting points from the monograph: 1. "A direct comparison of cpu times shows that the new method beats MPSX/370 - a commercial implementation of the simplex method - by more that a factor of 50 on problems with several thousand variables. Moreover, the relative advantage over the simplex method grows with the size of the problem." 2. As with the simplex algorithm, there is a gap between its worst- case behavior and its average behavior in actual use. 3. The algorithm is "easily" extended to nonlinear convex programming problems. 4. The existence of this algorithm reestablishes Turing's model of computation. Briefly, Turing said a "good" algorithm is a polynomial- time algorithm. The only previously known polynomial-time algorithm for linear programming, the ellipsoid method, was slower in practice than the simplex method (an exponential-time method), thus casting doubt on Turing's conjecture. I don't know when Karmarkar's paper is scheduled for publication. I got my pre-publication copy on October 1. David L. Rick Loveland Instrument Division Hewlett-Packard Company hplabs!hplvla!hplvle
paulv@boring.UUCP (01/15/85)
In article <7700001@hplvle.UUCP> drick@hplvle.UUCP (drick) writes: >[bug food] >0. Karmarkar's paper has not been published yet. >1. "A direct comparison of cpu times shows that the new method beats >MPSX/370 - a commercial implementation of the simplex method - by more >than a factor of 50 on problems with several thousand variables. >4. The existence of this algorithm reestablishes Turing's model of >computation. Briefly, Turing said a "good" algorithm is a polynomial- >time algorithm. The only previously known polynomial-time algorithm >for linear programming, the ellipsoid method, was slower in practice >than the simplex method (an exponential-time method), thus casting >doubt on Turing's conjecture. >David L. Rick >Loveland Instrument Division >Hewlett-Packard Company >hplabs!hplvla!hplvle 0. Karmarkar's method appears in the Proceedings of the 16th ACM Symposium on Theory of Computing, Washington D.C., April-May 1984, pp 302-311 (ACM Order #508840). 1. It is claimed to have beaten the blah package for some specific problems, not for all problems. Maybe K's Algorithm runs better only on this eclectic set. 4. The algorithm has not more to do with T's model of computation than any other algorithm. Turing had been dead for over a decade (and his paper published for thirty years) before somebody (Cobham-Hartmanis- Stearns-Cook-Karp '65~'70s) started talking about polynomial time algorithms. The simplexmethod runs in linear time for most *real-life* problems, but can be forced to spend exponential time on some *cooked-up* problems. It was unknown whether LP was as difficult as a large class of problems (NP-Complete Problems) for which only exponential *worst-case* time algorithms are known. When Khachians Ellipsoid Algorithm came along (1979) it was shown that LP is not difficult, in that sense, i.e., the latter algorithm has a polynomial worst-case running time. For *practical* use the simplexmethod appeared to perform better. The Karmarkar algorithm is *claimed* to perform not only better than any other in the *theoretically* interesting *worst-case*, but also in *practical use*. About the latter claim there is no consensus at all; a lot of investigation is going on. The worst-case running time of K's algorithm is worse than what is considered acceptable for a common run of Simplex; the question is whether it in general performs better on common natural problems than does Simplex. Nothing in this story throws, or has thrown, any doubt on Turing's or anybody elses conjectures. It has no bearing on the value of any model of computation.
bjpt@mulga.OZ (Benjamin Thompson) (01/18/85)
In article <6285@boring.UUCP> paulv@boring.UUCP (Paul Vitanyi) writes: > ... It was unknown whether LP was as >difficult as a large class of problems (NP-Complete Problems) for >which only exponential *worst-case* time algorithms are known. When >Khachians Ellipsoid Algorithm came along (1979) it was shown >that LP is not difficult, in that sense, i.e., the latter algorithm >has a polynomial worst-case running time. Khachian's algorithm being polynomial time does *not* mean that LP is not an NP-complete problem. To draw this conclusion, one has to make the as-yet *unproven* assumption that NP is not equal to P. Ben Thompson, {decvax,vax135}!mulga!bjpt
paulv@boring.UUCP (01/23/85)
In article <612@mulga.OZ> bjpt@mulga.OZ (Benjamin Thompson) writes: >In article <6285@boring.UUCP> paulv@boring.UUCP (Paul Vitanyi) writes: >> ... It was unknown whether LP was as >>difficult as a large class of problems (NP-Complete Problems) for >>which only exponential *worst-case* time algorithms are known. When >>Khachians Ellipsoid Algorithm came along (1979) it was shown >>that LP is not difficult, in that sense, i.e., the latter algorithm >>has a polynomial worst-case running time. > > >Khachian's algorithm being polynomial time does *not* mean that LP is not >an NP-complete problem. To draw this conclusion, one has to make the >as-yet *unproven* assumption that NP is not equal to P. > > Ben Thompson, {decvax,vax135}!mulga!bjpt If P=NP then every problem in P (and NP) is vacuously NP-complete.