Talk:Karmarkar's algorithm

Put into simpler english please!

Do you think any layman with a passing interest in super-computing can understand this? -- unsigned by 24.56.163.174, 1 July 2007

Seconded. Mostly I am missing a section with examples. What is this algorithm good for in real life? --BjKa (talk) 11:08, 18 August 2014 (UTC)

Confusing

An article about "Karmarkar's algorithm" under the heading "The Algorithm" should present Karmarkar's algorithm and not something else just because the real thing is "rather complicated".
I don't really feel confident enough about interior-point methods to write anything for the article... I _would_ feel ok trying to give an explanation of Karmarkar's algorithm here in the discussion section first for review by some senior mathematicians... Does anyone feel like volunteering for fact checking anything I might put together? —Preceding unsigned comment added by 84.75.149.134 (talk) 21:39, 30 January 2008 (UTC)

Inaccurate

This article is describing the affine-scaling algorithm, not Karmarkar's projective algorithm. Even the canonical form is lost, as are all the geometric ideas!
This is a better source.

• Strang, Gilbert (1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2). New York: Springer: 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. {{cite journal}}: Invalid |ref=harv (help)

--  Kiefer.Wolfowitz 01:55, 14 July 2011 (UTC)

Paragraph about patent law

PraeceptorIP (talk · contribs) has been pushing to include a paragraph on patent law in this article, about how "mathematics cannot be patented"; see e.g. this diff. My position is that this has not been tested against the Karmarkar patent (and will not ever be tested because the patent has expired) and therefore that its relevance here is original research by synthesis, not allowed without reliable sources that directly connect this case to Karmarkar's patent. But as always I welcome additional opinions. —David Eppstein (talk) 18:46, 6 December 2016 (UTC)

Thank you for stating your views, David. The title of this section of the article is "Patent controversy — Can mathematics be patented?" Until a few days ago, this part of the article contained no discussion of whether mathematics can be patented and no answer to the question posed in the section heading. Yet, the US Supreme Court has definitively answered the question and several of its decisions (quoted in the text to which you object) give a firm NO answer. The article as it stood was confusing or misleading, because it posed a question and indicated (wrongly) that the question was unresolved.

You state that the question "has not been tested against the Karmarkar patent (and will not ever be tested because the patent has expired). The question does not need to be tested against the expired Karmarkar patent. That is not how the law works. If it is indisputable that algorithms cannot be validly patented (as the Supreme Court has ruled in the cited cases), and it is undisputed that the Karmarkar Algorithm is an algorithm, then the Karmarkar Algorithm patent is not a valid patent, at least to the extent that it claims an algorithm as such. When the law is clear that all X's are Y, then any instance of X is Y. That is not synthesis or original research. It is just common sense, not OR or synthesis.

Nobody with any knowledge of patent law thinks that mathematics can be patented. It makes no difference that this patent has expired. The general rule applies. The Supreme Court has said over and over again that natural laws, like the Pythagorean Theorem, for example, belong to the public domain and therefore cannot be patented. They are the tools of scientific progress and it would be contrary to the public interest to allow a monopoly on them.

I am therefore reverting your last undo because the rule in Wikipedia is that you let the disputed text of the article stand until there is a consensus to remove it. This material is well sourced and any person with knowledge of patent law would agree with it. There is as yet no consensus to remove it. — PraeceptorIP (talk) 20:05, 6 December 2016 (UTC)

That is not how WP:BRD works. The rule is that if a text addition is disputed, it stays out until the discussion reaches a consensus. Please revert your addition until we complete this discussion. And again, the question is not whether a mathematical formula can be patented (clearly, no) but whether Karmarkar's algorithm counts as a "formula" or "mathematical principle" for the purposes of this point of law. We have no sources on that question. By placing this paragraph where you did, you implied that the rulings clearly would apply to Karmarkar's algorithm, when it is not at all clear. The fact that it is not clear is obvious (without any legal understanding necessary) from the fact that two of the three rulings cited in the patent happened before the patent was granted, and yet it was in fact granted. —David Eppstein (talk) 20:31, 6 December 2016 (UTC)

David, it does not matter that the patent office granted the patent. The overwhelming majority of software patents and business method patents that the patent office granted and that have been litigated have been held invalid by the courts. Also, not only is it immaterial that the rulings happened before the patent was granted. The latest Supreme Court decision governs over all others. Why don't you confer about this with someone in the law school faculty at your university. Your doubtless well meaning and good faith comments are based on a misunderstanding of the legal system and in particular of patent law. A fellow faculty member would set you straight.

You say: "We have no sources on that question [whether algorithms are unpatentable mathematics]." The Supreme Court's Benson and Flook decisions each involved algorithms, and the Court held that the algorithms in those cases could not be patented because they were mathematics. (If you are in doubt, read the Supreme Court opinions.)

And I hope you do not find this distressing, but the Eppstein Algorithm, as such, cannot be the subject of a valid patent. It might have been patented, however, if implemented in an inventive manner. See Narrowly Drawn Software-Based Patent Claims Directed To Specific, Unconventional Technological Solutions Are Patent-Eligible Under Alice, iPFrontline (Nov. 14, 2016); see also Diamond v. Diehr. However, the Nov. 2016 decision may be appealed. PraeceptorIP (talk) 21:40, 6 December 2016 (UTC)

I am coinventor on one algorithm patent but it's not on something called the Eppstein algorithm and is irrelevant to this discussion. And I am happy enough with the state of things being that "algorithms cannot be patented". But I don't think the sources you used for that make this case, because some of them are about mathematical formulas (that is to say, facts) rather than algorithms (processes). In any case, I don't think the question for this article should be whether algorithms can be patented, except to the extent that the Karmarkar algorithm kicked off that broader issue. I think the question should be, was it appropriate to allow a patent on the Karmarkar algorithm? For that we need legal scholarship that discuss that patent specifically, not just pointers to arguably-relevant court cases. —David Eppstein (talk) 21:50, 6 December 2016 (UTC)

There are references to Eppstein's algorithm in https://wiki.riteme.site/wiki/K_shortest_path_routing#Paths_are_not_required_to_be_loopless - but if you say it's not relevant, OK.

I would not presume to volunteer an opinion on Disney's patent US Pat No 8,681,145 - but I sure would get an outside counsel's opinion on validity before I tried to enforce it. But that's irrelevant to this discussion, too - isn't it?

It is incorrect to distinguish (as above) between "mathematical formulas (that is to say, facts) rather than algorithms (processes)" -- Both things cannot be patented under current US law. See the previously cited cases.

Maybe the whole problem is the title of the section - "Patent controversy — Can mathematics be patented?" Maybe that title should be changed, because it is clear US law that mathematics cannot be patented. To answer the somewhat different question - was it appropriate to allow a patent on the Karmarkar algorithm? - you need to use the normal methods by which legal questions get answered. For an answer to that, you could look at the Supreme Court's Flook opinion, which sets out the algorithm in an appendix and in the body of the opinion explains why the algorithm cannot validly be patented. You cannot expect to get a discussion of any specific algorithm unless there is a reported patent infringement case on that algorithm patent. Ordinarily, legal questions are answered by looking to analogous cases and extrapolating from them. Sometimes the answer from extrapolation is very clear, sometimes not, but it is very clear that no algorithm as such can be validly patented under US patent law. Therefore, a patent on the Karmarkar algorithm as an algorithm would violate US law and such a patent would be held invalid by the US courts. Maybe the whole section titled "Patent controversy — Can mathematics be patented?" should be rewritten, starting with the title. I would be glad to cooperate with you on that if you wanted to do so. -- PraeceptorIP (talk) 22:47, 6 December 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Karmarkar's algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf to http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 16:49, 6 December 2017 (UTC)