[Patents] Re: Konno 1995: The Karmarkar patent and Software -- does math patenting work?

[mva@df.lth.se (Martin Wahlén)]

> The patent was granted in 1988.  From 1984-88 Karmarkar and AT&T were very
> secretive about the effectiveness of their algorithm and provoked academic
> conferences by just bragging and not answering questions.  That is why the
> academic community engaged in its own research and by 1988, when they
> found out that Karmarkar/AT&T had obtained a patent, had already
> significantly improved on the methods of Karmarkar.

No! Karmarkars method was not proven to be good in all cases, the time
complexity was proven to be polynomial, but people were not sure of the
practicalness of the algorithm. The theoretical breakthrough was the
elipsoid method, karmakars algorithm was the first practical algorithm
but:

The algorithm is quite hard to understand and it is not "obvious" to me
that the constant factors are small enough that we could create practical
implementations. This was also true for a number of researchers that I
have talked with who did investigate other interiorpoint methods.

Martin