HOME

TheInfoList



OR:

Karmarkar's algorithm is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
introduced by
Narendra Karmarkar Narendra Krishna Karmarkar (born Circa 1956) is an Indian Mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher. He invented one of the first provably polynomial time algorithms for linear prog ...
in 1984 for solving
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
problems. It was the first reasonably efficient algorithm that solves these problems in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
. The
ellipsoid method In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algor ...
is also polynomial time but proved to be inefficient in practice. Denoting n as the number of variables and L as the number of bits of input to the algorithm, Karmarkar's algorithm requires O(n^ L) operations on O(L) digit numbers, as compared to O(n^6 L) such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus :O(n^ L^2 \cdot \log L \cdot \log \log L) using FFT-based multiplication (see
Big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
). Karmarkar's algorithm falls within the class of
interior point method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in ...
s: the current guess for the solution does not follow the boundary of the
feasible set In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
as in the
simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
, but it moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data.


The algorithm

Consider a linear programming problem in matrix form: Karmarkar's algorithm determines the next feasible direction toward optimality and scales back by a factor . It is described in a number of sources. Karmarkar also has extended the method to solve problems with integer constraints and non-convex problems. Since the actual algorithm is rather complicated, researchers looked for a more intuitive version of it, and in 1985 developed affine scaling, a version of Karmarkar's algorithm that uses
affine transformation In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generall ...
s where Karmarkar used projective ones, only to realize four years later that they had rediscovered an algorithm published by
Soviet The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen nationa ...
mathematician I. I. Dikin in 1967. The affine-scaling method can be described succinctly as follows. The affine-scaling algorithm, while applicable to small scale problems, is not a polynomial time algorithm. ''stopping criterion'', . return unbounded end if end do


Example

Consider the linear program : \begin \text & x_1 + x_2 \\ \text & 2p x_1 + x_2 & \leq & p^2+1, & p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0. \end That is, there are 2 variables x_1, x_2 and 11 constraints associated with varying values of p. This figure shows each iteration of the algorithm as red circle points. The constraints are shown as blue lines.


Patent controversy – can mathematics be patented?

At the time he invented the algorithm, Karmarkar was employed by IBM as a postdoctoral fellow in the IBM San Jose Research Laboratory in California. On August 11, 1983 he gave a seminar at
Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is conside ...
explaining the algorithm, with his affiliation still listed as IBM. By the fall of 1983 Karmarkar started to work at
AT&T AT&T Inc. is an American multinational telecommunications holding company headquartered at Whitacre Tower in Downtown Dallas, Texas. It is the world's largest telecommunications company by revenue and the third largest provider of mobile te ...
and submitted his paper to the 1984 ACM
Symposium on Theory of Computing The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for ...
(STOC, held April 30 - May 2, 1984) stating
AT&T Bell Laboratories Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
as his affiliation. After applying the algorithm to optimizing AT&T's telephone network, they realized that his invention could be of practical importance. In April 1985, AT&T promptly applied for a patent on his algorithm. The patent became more fuel for the ongoing controversy over the issue of
software patent A software patent is a patent on a piece of software, such as a computer program, libraries, user interface, or algorithm. Background A patent is a set of exclusionary rights granted by a state to a patent holder for a limited period of time, ...
s. This left many mathematicians uneasy, such as Ronald Rivest (himself one of the holders of the patent on the RSA algorithm), who expressed the opinion that research proceeded on the basis that algorithms should be free. Even before the patent was actually granted, it was argued that there might have been
prior art Prior art (also known as state of the art or background art) is a concept in patent law used to determine the patentability of an invention, in particular whether an invention meets the novelty and the inventive step or non-obviousness criteria ...
that was applicable.Various posts by Matthew Saltzman, Clemson University
/ref> Mathematicians who specialized in
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods t ...
, including Philip Gill and others, claimed that Karmarkar's algorithm is equivalent to a projected Newton barrier method with a logarithmic
barrier function In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region of an optimization problem. Such functions are ...
, if the parameters are chosen suitably. Legal scholar Andrew Chin opines that Gill's argument was flawed, insofar as the method they describe does not constitute an "algorithm", since it requires choices of parameters that don't follow from the internal logic of the method, but rely on external guidance, essentially from Karmarkar's algorithm. Furthermore, Karmarkar's contributions are considered far from obvious in light of all prior work, including Fiacco-McCormick, Gill and others cited by Saltzman.Mark A. Paley (1995). "The Karmarkar Patent: Why Congress Should "Open the Door" to Algorithms as Patentable Subject Matter". 22 Computer L. Rep. 7 The patent was debated in the U.S. Senate and granted in recognition of the essential originality of Karmarkar's work, as : "Methods and apparatus for efficient resource allocation" in May 1988. AT&T designed a
vector Vector most often refers to: *Euclidean vector, a quantity with a magnitude and a direction *Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematic ...
multi-processor Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
computer system specifically to run Karmarkar's algorithm, calling the resulting combination of hardware and software KORBX, and marketed this system at a price of US$8.9 million. Its first customer was the
Pentagon In geometry, a pentagon (from the Greek πέντε ''pente'' meaning ''five'' and γωνία ''gonia'' meaning ''angle'') is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°. A pentagon may be sim ...
. Opponents of software patents have further argued that the patents ruined the positive interaction cycles that previously characterized the relationship between researchers in linear programming and industry, and specifically it isolated Karmarkar himself from the network of mathematical researchers in his field. The patent itself expired in April 2006, and the algorithm is presently in the
public domain The public domain (PD) consists of all the creative work to which no exclusive intellectual property rights apply. Those rights may have expired, been forfeited, expressly waived, or may be inapplicable. Because those rights have expired, ...
. The
United States Supreme Court The Supreme Court of the United States (SCOTUS) is the highest court in the federal judiciary of the United States. It has ultimate appellate jurisdiction over all U.S. Federal tribunals in the United States, federal court cases, and over Stat ...
has held that mathematics cannot be patented in ''
Gottschalk v. Benson ''Gottschalk v. Benson'', 409 U.S. 63 (1972), was a United States Supreme Court case in which the Court ruled that a process claim directed to a numerical algorithm, as such, was not patentable because "the patent would ''wholly pre-empt'' the ma ...
'', In that case, the Court first addressed whether computer algorithms could be patented and it held that they could not because the patent system does not protect ideas and similar abstractions. In ''
Diamond v. Diehr ''Diamond v. Diehr'', 450 U.S. 175 (1981), was a United States Supreme Court decision which held that controlling the execution of a physical process, by running a computer program did not preclude patentability of the invention as a whole. The hi ...
'', the Supreme Court stated, "A mathematical formula as such is not accorded the protection of our patent laws, and this principle cannot be circumvented by attempting to limit the use of the formula to a particular technological environment. In '' Mayo Collaborative Services v. Prometheus Labs., Inc.'', the Supreme Court explained further that "simply implementing a mathematical principle on a physical machine, namely a computer, not a patentable application of that principle."Accord '' Alice Corp. v. CLS Bank Int’l'', 573 U.S. __, 134 S. Ct. 2347 (2014).


References

* * Narendra Karmarkar (1984).
A New Polynomial Time Algorithm for Linear Programming
, ''
Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honora ...
'', Vol 4, nr. 4, p. 373–395. {{DEFAULTSORT:Karmarkar's Algorithm Optimization algorithms and methods Articles with example pseudocode Software patent law Linear programming