1510:, 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. The patent was debated in the U.S. Senate and granted in recognition of the essential originality of Karmarkar's work, as
2694:
1207:
1377:
1534:
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
1927:
26. Karmarkar, N. K., Thakur, S. A., An
Interior Point Approach to a Tensor Optimisation Problem with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of Second Conference on Integer Programming and Combinatorial Optimisation, (May
1060:
1220:
1561:, 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
1474:
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.
737:
1917:
Karmarkar, N. K. and Kamath, A. P., A continuous
Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press
2053:
Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and
Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June
2096:
Gill, Philip E.; Murray, Walter; Saunders, Michael A.; Tomlin, J. A.; Wright, Margaret H. (1986). "On projected Newton barrier methods for linear programming and an equivalence to
Karmarkar's projective method".
452:, but 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.
1526:
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
424:
818:
1555:, 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
1123:
1490:
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
918:
2591:
655:
527:
mathematician I. I. Dikin in 1967. The affine-scaling method can be described succinctly as follows. While applicable to small scale problems, it is not a polynomial time algorithm.
1567:, the Supreme Court explained further that "simply implementing a mathematical principle on a physical machine, namely a computer, s not a patentable application of that principle."
865:
1372:{\displaystyle {\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}}
1563:
144:
1156:
227:
594:
1908:
Karmarkar, N.K., Interior Point
Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)
1420:
902:
274:
2462:
342:
2363:
1899:
Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series
Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
2586:
556:
303:
173:
1440:
95:
71:
3182:
1937:
27. Kamath, A., Karmarkar, N. K., A Continuous Method for
Computing Bounds in Integer Quadratic Optimisation Problems, Journal of Global Optimization (1992).
661:
2160:
Mark A. Paley (1995). "The
Karmarkar Patent: Why Congress Should "Open the Door" to Algorithms as Patentable Subject Matter". 22 Computer L. Rep. 7
501:. It is described in a number of sources. Karmarkar also has extended the method to solve problems with integer constraints and non-convex problems.
2600:
3080:
1946:
Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization. Springer Lecture Notes in Computer Science LNCS 6457, Dec 2010
1651:
2455:
1622:
430:
3161:
2623:
1528:
2675:
2536:
2643:
2431:
2246:
350:
2754:
2448:
1467:
1455:
2359:
2171:
511:
Since the actual algorithm is rather complicated, researchers looked for a more intuitive version of it, and in 1985 developed
743:
3031:
2693:
1744:
1672:
2360:"ä»é攩: ă«ăŒăăŒă«ăŒçčèš±ăšăœăăăŠă§ăą â æ°ćŠăŻ çčèš±ă« ăȘăă (Konno Hiroshi: The Kamarkar Patent and Software â Has Mathematics Become Patentable?)"
3139:
2759:
1167:
1066:
3075:
3043:
3187:
2084:
3192:
3124:
2749:
2283:
1546:
1055:{\displaystyle \alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}}
3070:
3026:
2628:
2065:
1503:
1462:
explaining the algorithm, with his affiliation still listed as IBM. By the fall of 1983 Karmarkar started to work at
2919:
2648:
1442:. This figure shows each iteration of the algorithm as red circle points. The constraints are shown as blue lines.
2809:
2471:
1471:
2994:
2387:
409 U.S. 63 (1972). The case concerned an algorithm for converting binary-coded decimal numerals to pure binary.
1956:
Vanderbei, R. J.; Lagarias, J. C. (1990). "I. I. Dikin's convergence result for the affine-scaling algorithm".
611:
824:
3038:
2937:
2653:
2411:, 437 U.S. 584, 585 (1978) ("the discovery of a novel and useful mathematical formula may not be patented").
1991:
1960:. Contemporary Mathematics. Vol. 114. Providence, RI: American Mathematical Society. pp. 109â119.
1869:
Karmarkar, Narendra (1990). "Riemannian geometry underlying interior-point methods for linear programming".
1842:. Contemporary Mathematics. Vol. 114. Providence, RI: American Mathematical Society. pp. 297â308.
2531:
497:
Karmarkar's algorithm determines the next feasible direction toward optimality and scales back by a factor
3129:
3114:
3004:
2882:
2508:
2475:
1873:. Contemporary Mathematics. Vol. 114. Providence, RI: American Mathematical Society. pp. 51â75.
3018:
2984:
2887:
2829:
2710:
2516:
2496:
516:
441:
2172:"The Interior-Point Revolution in Optimization: History, Recent Developments, and Lasting Consequences"
2137:"On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens"
100:
3065:
2892:
2804:
2136:
1551:
1129:
2440:
2032:
178:
3134:
2999:
2952:
2942:
2794:
2782:
2595:
2578:
2483:
2207:
1987:
1459:
573:
520:
2869:
2838:
2824:
2814:
2605:
2341:
2227:
2114:
2070:
2014:
1820:
1785:
1750:
1705:
1610:
1499:
1495:
1385:
1225:
874:
240:
39:
35:
2521:
308:
2877:
2555:
1740:
1689:
1593:; Veiga, Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming".
2957:
2947:
2851:
2728:
2633:
2615:
2568:
2479:
2333:
2306:
2219:
2186:
2106:
2006:
1961:
1874:
1843:
1812:
1777:
1732:
1681:
1602:
1590:
1557:
1520:
1507:
523:
ones, only to realize four years later that they had rediscovered an algorithm published by
47:
1973:
1886:
1855:
1701:
534:
2973:
2407:
1969:
1882:
1851:
1697:
1523:
1487:
1479:
344:
such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus
279:
149:
43:
2257:
42:
problems. It was the first reasonably efficient algorithm that solves these problems in
2961:
2846:
2733:
2667:
2638:
2223:
1816:
1667:
1425:
512:
449:
434:
80:
56:
2301:
3176:
3119:
3103:
2367:
1838:
Karmarkar, Narendra (1990). "An interior-point approach to NP-complete problems. I".
1803:
Karmarkar, Narendra K. (1989). "Power Series Variants of Karmarkar-Type Algorithms".
1709:
1627:
1539:
1483:
2345:
2231:
2118:
1824:
1754:
1614:
3057:
2563:
1789:
1729:
Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84
524:
445:
2191:
2018:
732:{\displaystyle D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})}
1965:
1878:
1847:
17:
3144:
2526:
1768:
Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming".
2247:"AT&T markets problem solver, based on math whiz's find, for $ 8.9 million"
1958:
Mathematical developments arising from linear programming (Brunswick, ME, 1988)
1871:
Mathematical developments arising from linear programming (Brunswick, ME, 1988)
1840:
Mathematical developments arising from linear programming (Brunswick, ME, 1988)
1575:
Karmarkar's algorithm was used by the US Army for logistic planning during the
1538:
The patent itself expired in April 2006, and the algorithm is presently in the
1512:
1693:
1670:(1 June 1987). "Karmarkar's algorithm and its place in applied mathematics".
97:
the number of bits of input to the algorithm, Karmarkar's algorithm requires
2066:"IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes"
1491:
31:
2337:
1724:
2328:
Kennington, J.L. (1989). "Using KORBX for military airlift applications".
1736:
1478:
The patent became more fuel for the ongoing controversy over the issue of
2546:
1576:
1516:: "Methods and apparatus for efficient resource allocation" in May 1988.
444:: the current guess for the solution does not follow the boundary of the
229:
such operations for the ellipsoid algorithm. In "square" problems, when
2866:
2110:
2010:
1781:
1685:
1606:
1463:
1206:
1502:
and others, claimed that Karmarkar's algorithm is equivalent to a
1205:
50:
is also polynomial time but proved to be inefficient in practice.
1450:
At the time he invented the algorithm, Karmarkar was employed by
3101:
2917:
2780:
2708:
2494:
2444:
2330:
Proceedings of the 28th IEEE Conference on Decision and Control
2206:
Marc S. Meketon; Y.C. Cheng; D.J. Houck; J.M.Liu; L. Slutsman;
1451:
419:{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),}
2692:
1992:"A Modification of Karmarkar's Linear Programming Algorithm"
1653:
Interior point polynomial-time methods in convex programming
2302:"Military Is First Announced Customer Of AT&T Software"
1195:" terminates the algorithm and outputs the following value.
1725:"A new polynomial-time algorithm for linear programming"
1645:
1643:
813:{\displaystyle h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c}
1494:
that was applicable. Mathematicians who specialized in
1458:
in California. On August 11, 1983 he gave a seminar at
1623:
A New Polynomial Time Algorithm for Linear Programming
460:
Consider a linear programming problem in matrix form:
2085:
Various posts by Matthew Saltzman, Clemson University
1564:
Mayo Collaborative Services v. Prometheus Labs., Inc.
1428:
1422:
and 11 constraints associated with varying values of
1388:
1223:
1132:
1069:
921:
877:
827:
746:
664:
614:
576:
537:
353:
311:
282:
243:
181:
152:
103:
83:
59:
1118:{\displaystyle x^{k+1}\leftarrow x^{k}+\alpha h_{x}}
3056:
3017:
2983:
2972:
2930:
2865:
2837:
2823:
2793:
2742:
2721:
2666:
2614:
2577:
2554:
2545:
2507:
1434:
1414:
1371:
1150:
1117:
1054:
896:
859:
812:
731:
649:
588:
550:
418:
336:
297:
268:
221:
167:
138:
89:
65:
1486:(himself one of the holders of the patent on the
1482:. This left many mathematicians uneasy, such as
1549:has held that mathematics cannot be patented in
934:
440:Karmarkar's algorithm falls within the class of
2210:; P. Wang (1989). "The AT&T KORBX System".
515:, a version of Karmarkar's algorithm that uses
2456:
2179:Bulletin of the American Mathematical Society
8:
1470:(STOC, held April 30 - May 2, 1984) stating
1049:
937:
2284:"Big A.T.&T. Computer for Complexities"
3098:
3014:
2980:
2927:
2914:
2834:
2790:
2777:
2718:
2705:
2551:
2504:
2491:
2463:
2449:
2441:
77:the number of inequality constraints, and
2190:
1990:; Meketon, Marc; Freedman, Barry (1986).
1427:
1406:
1393:
1387:
1309:
1292:
1279:
1262:
1252:
1239:
1228:
1224:
1222:
1131:
1109:
1093:
1074:
1068:
1027:
1012:
1002:
994:
993:
988:
987:
986:
980:
970:
958:
952:
947:
920:
882:
876:
851:
832:
826:
798:
782:
777:
767:
751:
745:
720:
715:
696:
691:
669:
663:
641:
619:
613:
575:
542:
536:
374:
364:
352:
322:
310:
281:
254:
242:
192:
180:
151:
124:
114:
102:
82:
58:
2697:Optimization computes maxima and minima.
2435:, 573 U.S. __, 134 S. Ct. 2347 (2014).
1466:and submitted his paper to the 1984 ACM
650:{\displaystyle v^{k}\leftarrow b-Ax^{k}}
2130:
2128:
1639:
860:{\displaystyle h_{v}\leftarrow -Ah_{x}}
2893:Principal pivoting algorithm of Lemke
7:
2420:566 U.S. __, 132 S. Ct. 1289 (2012).
2245:Lowenstein, Roger (15 August 1988).
2144:Journal of Intellectual Property Law
3183:Optimization algorithms and methods
2537:Successive parabolic interpolation
2224:10.1002/j.1538-7305.1989.tb00315.x
1817:10.1002/j.1538-7305.1989.tb00316.x
1589:Adler, Ilan; Karmarkar, Narendra;
237:), Karmarkar's algorithm requires
25:
2857:Projective algorithm of Karmarkar
2852:Ellipsoid algorithm of Khachiyan
2755:Sequential quadratic programming
2592:BroydenâFletcherâGoldfarbâShanno
2282:Markoff, John (13 August 1988).
1468:Symposium on Theory of Computing
1456:IBM San Jose Research Laboratory
1454:as a postdoctoral fellow in the
139:{\displaystyle O(m^{1.5}n^{2}L)}
1635:, nr. 4, p. 373–395.
1504:projected Newton barrier method
1382:That is, there are 2 variables
1151:{\displaystyle k\leftarrow k+1}
305:-digit numbers, as compared to
175:-digit numbers, as compared to
2810:Reduced gradient (FrankâWolfe)
1673:The Mathematical Intelligencer
1136:
1086:
1009:
995:
989:
977:
963:
925:
838:
795:
760:
757:
726:
684:
675:
625:
580:
410:
357:
331:
315:
292:
286:
263:
247:
222:{\displaystyle O(n^{3}(n+m)L)}
216:
210:
198:
185:
162:
156:
133:
107:
1:
3140:Spiral optimization algorithm
2760:Successive linear programming
2432:Alice Corp. v. CLS Bank Intâl
2192:10.1090/S0273-0979-04-01040-7
589:{\displaystyle k\leftarrow 0}
2878:Simplex algorithm of Dantzig
2750:Augmented Lagrangian methods
1621:Narendra Karmarkar (1984). "
1214:Consider the linear program
2170:Margaret H. Wright (2004).
2064:Kolata, Gina (1989-03-12).
1547:United States Supreme Court
1415:{\displaystyle x_{1},x_{2}}
897:{\displaystyle h_{v}\geq 0}
269:{\displaystyle O(n^{3.5}L)}
3209:
2405:450 U.S. at 191. See also
2212:AT&T Technical Journal
1805:AT&T Technical Journal
1650:Arkadi Nemirovsky (2004).
1472:AT&T Bell Laboratories
1178:" means that the value of
3157:
3110:
3097:
3081:Pushârelabel maximum flow
2926:
2913:
2883:Revised simplex algorithm
2789:
2776:
2717:
2704:
2690:
2503:
2490:
465:
337:{\displaystyle O(n^{4}L)}
73:the number of variables,
2606:Symmetric rank-one (SR1)
2587:BerndtâHallâHallâHausman
2099:Mathematical Programming
1966:10.1090/conm/114/1097868
1879:10.1090/conm/114/1097865
1848:10.1090/conm/114/1097880
1595:Mathematical Programming
1182:changes to the value of
431:FFT-based multiplication
3130:Parallel metaheuristics
2938:Approximation algorithm
2649:Powell's dog leg method
2601:DavidonâFletcherâPowell
2497:Unconstrained nonlinear
3115:Evolutionary algorithm
2698:
2338:10.1109/CDC.1989.70419
2332:. pp. 1603â1605.
1723:Karmarkar, N. (1984).
1591:Resende, Mauricio G.C.
1436:
1416:
1373:
1211:
1152:
1119:
1056:
898:
861:
814:
733:
651:
590:
552:
517:affine transformations
442:interior-point methods
420:
338:
299:
270:
223:
169:
140:
91:
67:
2888:Criss-cross algorithm
2711:Constrained nonlinear
2696:
2517:Golden-section search
1737:10.1145/800057.808695
1513:U.S. patent 4,744,028
1437:
1417:
1374:
1209:
1153:
1120:
1057:
899:
862:
815:
734:
652:
591:
553:
551:{\displaystyle x^{0}}
519:where Karmarkar used
421:
339:
300:
271:
224:
170:
141:
92:
68:
28:Karmarkar's algorithm
2805:Cutting-plane method
2396:450 U.S. 175 (1981).
2135:Andrew Chin (2009).
1731:. pp. 302â311.
1552:Gottschalk v. Benson
1519:AT&T designed a
1426:
1386:
1221:
1130:
1067:
919:
875:
825:
744:
662:
612:
574:
535:
351:
309:
298:{\displaystyle O(L)}
280:
241:
179:
168:{\displaystyle O(L)}
150:
101:
81:
57:
38:in 1984 for solving
3188:Software patent law
3135:Simulated annealing
2953:Integer programming
2943:Dynamic programming
2783:Convex optimization
2644:LevenbergâMarquardt
2254:Wall Street Journal
2208:Robert J. Vanderbei
2034:Karmarkar Algorithm
1988:Robert J. Vanderbei
1506:with a logarithmic
1460:Stanford University
957:
790:
725:
701:
3193:Linear programming
2815:Subgradient method
2699:
2624:Conjugate gradient
2532:NelderâMead method
2288:The New York Times
2111:10.1007/BF02592025
2071:The New York Times
2011:10.1007/BF01840454
1782:10.1007/BF02579150
1686:10.1007/BF03025891
1607:10.1007/bf01587095
1496:numerical analysis
1446:Patent controversy
1432:
1412:
1369:
1367:
1212:
1170:. For instance, "
1166:"←" denotes
1148:
1115:
1052:
943:
894:
857:
810:
773:
729:
711:
687:
647:
602:stopping criterion
586:
561:stopping criterion
548:
416:
334:
295:
266:
219:
165:
136:
87:
63:
40:linear programming
36:Narendra Karmarkar
3170:
3169:
3153:
3152:
3093:
3092:
3089:
3088:
3052:
3051:
3013:
3012:
2909:
2908:
2905:
2904:
2901:
2900:
2772:
2771:
2768:
2767:
2688:
2687:
2684:
2683:
2662:
2661:
1435:{\displaystyle p}
1265:
1231:
1196:
1187:
531:Input: A, b, c,
495:
494:
90:{\displaystyle L}
66:{\displaystyle n}
18:Projective method
16:(Redirected from
3200:
3099:
3015:
2981:
2958:Branch and bound
2948:Greedy algorithm
2928:
2915:
2835:
2791:
2778:
2719:
2706:
2654:Truncated Newton
2569:Wolfe conditions
2552:
2505:
2492:
2465:
2458:
2451:
2442:
2436:
2427:
2421:
2418:
2412:
2403:
2397:
2394:
2388:
2385:
2379:
2378:
2376:
2375:
2366:. Archived from
2356:
2350:
2349:
2325:
2319:
2318:
2316:
2315:
2307:Associated Press
2298:
2292:
2291:
2279:
2273:
2272:
2270:
2268:
2262:
2256:. Archived from
2251:
2242:
2236:
2235:
2203:
2197:
2196:
2194:
2176:
2167:
2161:
2158:
2152:
2151:
2141:
2132:
2123:
2122:
2093:
2087:
2082:
2076:
2075:
2061:
2055:
2051:
2045:
2044:
2043:
2042:
2029:
2023:
2022:
2005:(1â4): 395â407.
1996:
1984:
1978:
1977:
1953:
1947:
1944:
1938:
1935:
1929:
1925:
1919:
1915:
1909:
1906:
1900:
1897:
1891:
1890:
1866:
1860:
1859:
1835:
1829:
1828:
1800:
1794:
1793:
1765:
1759:
1758:
1720:
1714:
1713:
1664:
1658:
1657:
1647:
1618:
1601:(1â3): 297â335.
1558:Diamond v. Diehr
1515:
1508:barrier function
1480:software patents
1441:
1439:
1438:
1433:
1421:
1419:
1418:
1413:
1411:
1410:
1398:
1397:
1378:
1376:
1375:
1370:
1368:
1314:
1313:
1297:
1296:
1284:
1283:
1266:
1263:
1257:
1256:
1244:
1243:
1232:
1229:
1210:Example solution
1190:
1165:
1158:
1157:
1155:
1154:
1149:
1125:
1124:
1122:
1121:
1116:
1114:
1113:
1098:
1097:
1085:
1084:
1062:
1061:
1059:
1058:
1053:
1017:
1016:
1007:
1006:
992:
985:
984:
975:
974:
962:
956:
951:
907:
903:
901:
900:
895:
887:
886:
867:
866:
864:
863:
858:
856:
855:
837:
836:
820:
819:
817:
816:
811:
806:
805:
789:
781:
772:
771:
756:
755:
739:
738:
736:
735:
730:
724:
719:
700:
695:
674:
673:
657:
656:
654:
653:
648:
646:
645:
624:
623:
607:
596:
595:
593:
592:
587:
566:
559:
557:
555:
554:
549:
547:
546:
500:
490:
474:
463:
462:
425:
423:
422:
417:
379:
378:
369:
368:
343:
341:
340:
335:
327:
326:
304:
302:
301:
296:
275:
273:
272:
267:
259:
258:
228:
226:
225:
220:
197:
196:
174:
172:
171:
166:
145:
143:
142:
137:
129:
128:
119:
118:
96:
94:
93:
88:
72:
70:
69:
64:
48:ellipsoid method
21:
3208:
3207:
3203:
3202:
3201:
3199:
3198:
3197:
3173:
3172:
3171:
3166:
3149:
3106:
3085:
3048:
3009:
2986:
2975:
2968:
2922:
2897:
2861:
2828:
2819:
2796:
2785:
2764:
2738:
2734:Penalty methods
2729:Barrier methods
2713:
2700:
2680:
2676:Newton's method
2658:
2610:
2573:
2541:
2522:Powell's method
2499:
2486:
2469:
2439:
2428:
2424:
2419:
2415:
2408:Parker v. Flook
2404:
2400:
2395:
2391:
2386:
2382:
2373:
2371:
2358:
2357:
2353:
2327:
2326:
2322:
2313:
2311:
2300:
2299:
2295:
2281:
2280:
2276:
2266:
2264:
2260:
2249:
2244:
2243:
2239:
2205:
2204:
2200:
2174:
2169:
2168:
2164:
2159:
2155:
2139:
2134:
2133:
2126:
2095:
2094:
2090:
2083:
2079:
2063:
2062:
2058:
2052:
2048:
2040:
2038:
2031:
2030:
2026:
1994:
1986:
1985:
1981:
1955:
1954:
1950:
1945:
1941:
1936:
1932:
1926:
1922:
1916:
1912:
1907:
1903:
1898:
1894:
1868:
1867:
1863:
1837:
1836:
1832:
1802:
1801:
1797:
1767:
1766:
1762:
1747:
1722:
1721:
1717:
1668:Strang, Gilbert
1666:
1665:
1661:
1649:
1648:
1641:
1588:
1585:
1573:
1524:multi-processor
1511:
1448:
1424:
1423:
1402:
1389:
1384:
1383:
1366:
1365:
1324:
1305:
1303:
1298:
1288:
1275:
1267:
1259:
1258:
1248:
1235:
1233:
1219:
1218:
1204:
1199:
1162:
1128:
1127:
1126:
1105:
1089:
1070:
1065:
1064:
1063:
1008:
998:
976:
966:
917:
916:
915:
878:
873:
872:
868:
847:
828:
823:
822:
821:
794:
763:
747:
742:
741:
740:
665:
660:
659:
658:
637:
615:
610:
609:
608:
597:
572:
571:
570:
568:
564:
538:
533:
532:
530:
509:
508:Affine-Scaling
498:
482:
467:
458:
370:
360:
349:
348:
318:
307:
306:
278:
277:
250:
239:
238:
188:
177:
176:
148:
147:
120:
110:
99:
98:
79:
78:
55:
54:
44:polynomial time
23:
22:
15:
12:
11:
5:
3206:
3204:
3196:
3195:
3190:
3185:
3175:
3174:
3168:
3167:
3165:
3164:
3158:
3155:
3154:
3151:
3150:
3148:
3147:
3142:
3137:
3132:
3127:
3122:
3117:
3111:
3108:
3107:
3104:Metaheuristics
3102:
3095:
3094:
3091:
3090:
3087:
3086:
3084:
3083:
3078:
3076:FordâFulkerson
3073:
3068:
3062:
3060:
3054:
3053:
3050:
3049:
3047:
3046:
3044:FloydâWarshall
3041:
3036:
3035:
3034:
3023:
3021:
3011:
3010:
3008:
3007:
3002:
2997:
2991:
2989:
2978:
2970:
2969:
2967:
2966:
2965:
2964:
2950:
2945:
2940:
2934:
2932:
2924:
2923:
2918:
2911:
2910:
2907:
2906:
2903:
2902:
2899:
2898:
2896:
2895:
2890:
2885:
2880:
2874:
2872:
2863:
2862:
2860:
2859:
2854:
2849:
2847:Affine scaling
2843:
2841:
2839:Interior point
2832:
2821:
2820:
2818:
2817:
2812:
2807:
2801:
2799:
2787:
2786:
2781:
2774:
2773:
2770:
2769:
2766:
2765:
2763:
2762:
2757:
2752:
2746:
2744:
2743:Differentiable
2740:
2739:
2737:
2736:
2731:
2725:
2723:
2715:
2714:
2709:
2702:
2701:
2691:
2689:
2686:
2685:
2682:
2681:
2679:
2678:
2672:
2670:
2664:
2663:
2660:
2659:
2657:
2656:
2651:
2646:
2641:
2636:
2631:
2626:
2620:
2618:
2612:
2611:
2609:
2608:
2603:
2598:
2589:
2583:
2581:
2575:
2574:
2572:
2571:
2566:
2560:
2558:
2549:
2543:
2542:
2540:
2539:
2534:
2529:
2524:
2519:
2513:
2511:
2501:
2500:
2495:
2488:
2487:
2470:
2468:
2467:
2460:
2453:
2445:
2438:
2437:
2422:
2413:
2398:
2389:
2380:
2351:
2320:
2293:
2274:
2263:on 8 June 2016
2237:
2198:
2162:
2153:
2124:
2105:(2): 183â209.
2088:
2077:
2056:
2046:
2037:, IBM Research
2024:
1979:
1948:
1939:
1930:
1920:
1910:
1901:
1892:
1861:
1830:
1795:
1776:(4): 373â395.
1760:
1745:
1715:
1659:
1638:
1637:
1636:
1619:
1584:
1581:
1572:
1569:
1535:in his field.
1447:
1444:
1431:
1409:
1405:
1401:
1396:
1392:
1380:
1379:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1323:
1320:
1317:
1312:
1308:
1304:
1302:
1299:
1295:
1291:
1287:
1282:
1278:
1274:
1271:
1268:
1261:
1260:
1255:
1251:
1247:
1242:
1238:
1234:
1227:
1226:
1203:
1200:
1198:
1197:
1188:
1147:
1144:
1141:
1138:
1135:
1112:
1108:
1104:
1101:
1096:
1092:
1088:
1083:
1080:
1077:
1073:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1026:
1023:
1020:
1015:
1011:
1005:
1001:
997:
991:
983:
979:
973:
969:
965:
961:
955:
950:
946:
942:
939:
936:
933:
930:
927:
924:
911:unbounded
893:
890:
885:
881:
854:
850:
846:
843:
840:
835:
831:
809:
804:
801:
797:
793:
788:
785:
780:
776:
770:
766:
762:
759:
754:
750:
728:
723:
718:
714:
710:
707:
704:
699:
694:
690:
686:
683:
680:
677:
672:
668:
644:
640:
636:
633:
630:
627:
622:
618:
585:
582:
579:
569:
545:
541:
529:
513:affine scaling
504:
503:
493:
492:
480:
476:
475:
457:
454:
450:simplex method
435:Big O notation
427:
426:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
377:
373:
367:
363:
359:
356:
333:
330:
325:
321:
317:
314:
294:
291:
288:
285:
276:operations on
265:
262:
257:
253:
249:
246:
218:
215:
212:
209:
206:
203:
200:
195:
191:
187:
184:
164:
161:
158:
155:
146:operations on
135:
132:
127:
123:
117:
113:
109:
106:
86:
62:
34:introduced by
24:
14:
13:
10:
9:
6:
4:
3:
2:
3205:
3194:
3191:
3189:
3186:
3184:
3181:
3180:
3178:
3163:
3160:
3159:
3156:
3146:
3143:
3141:
3138:
3136:
3133:
3131:
3128:
3126:
3123:
3121:
3120:Hill climbing
3118:
3116:
3113:
3112:
3109:
3105:
3100:
3096:
3082:
3079:
3077:
3074:
3072:
3069:
3067:
3064:
3063:
3061:
3059:
3058:Network flows
3055:
3045:
3042:
3040:
3037:
3033:
3030:
3029:
3028:
3025:
3024:
3022:
3020:
3019:Shortest path
3016:
3006:
3003:
3001:
2998:
2996:
2993:
2992:
2990:
2988:
2987:spanning tree
2982:
2979:
2977:
2971:
2963:
2959:
2956:
2955:
2954:
2951:
2949:
2946:
2944:
2941:
2939:
2936:
2935:
2933:
2929:
2925:
2921:
2920:Combinatorial
2916:
2912:
2894:
2891:
2889:
2886:
2884:
2881:
2879:
2876:
2875:
2873:
2871:
2868:
2864:
2858:
2855:
2853:
2850:
2848:
2845:
2844:
2842:
2840:
2836:
2833:
2831:
2826:
2822:
2816:
2813:
2811:
2808:
2806:
2803:
2802:
2800:
2798:
2792:
2788:
2784:
2779:
2775:
2761:
2758:
2756:
2753:
2751:
2748:
2747:
2745:
2741:
2735:
2732:
2730:
2727:
2726:
2724:
2720:
2716:
2712:
2707:
2703:
2695:
2677:
2674:
2673:
2671:
2669:
2665:
2655:
2652:
2650:
2647:
2645:
2642:
2640:
2637:
2635:
2632:
2630:
2627:
2625:
2622:
2621:
2619:
2617:
2616:Other methods
2613:
2607:
2604:
2602:
2599:
2597:
2593:
2590:
2588:
2585:
2584:
2582:
2580:
2576:
2570:
2567:
2565:
2562:
2561:
2559:
2557:
2553:
2550:
2548:
2544:
2538:
2535:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2514:
2512:
2510:
2506:
2502:
2498:
2493:
2489:
2485:
2481:
2477:
2473:
2466:
2461:
2459:
2454:
2452:
2447:
2446:
2443:
2434:
2433:
2426:
2423:
2417:
2414:
2410:
2409:
2402:
2399:
2393:
2390:
2384:
2381:
2370:on 2008-06-27
2369:
2365:
2361:
2355:
2352:
2347:
2343:
2339:
2335:
2331:
2324:
2321:
2309:
2308:
2303:
2297:
2294:
2289:
2285:
2278:
2275:
2259:
2255:
2248:
2241:
2238:
2233:
2229:
2225:
2221:
2217:
2213:
2209:
2202:
2199:
2193:
2188:
2184:
2180:
2173:
2166:
2163:
2157:
2154:
2149:
2145:
2138:
2131:
2129:
2125:
2120:
2116:
2112:
2108:
2104:
2100:
2092:
2089:
2086:
2081:
2078:
2073:
2072:
2067:
2060:
2057:
2050:
2047:
2036:
2035:
2028:
2025:
2020:
2016:
2012:
2008:
2004:
2000:
1993:
1989:
1983:
1980:
1975:
1971:
1967:
1963:
1959:
1952:
1949:
1943:
1940:
1934:
1931:
1924:
1921:
1914:
1911:
1905:
1902:
1896:
1893:
1888:
1884:
1880:
1876:
1872:
1865:
1862:
1857:
1853:
1849:
1845:
1841:
1834:
1831:
1826:
1822:
1818:
1814:
1810:
1806:
1799:
1796:
1791:
1787:
1783:
1779:
1775:
1771:
1770:Combinatorica
1764:
1761:
1756:
1752:
1748:
1742:
1738:
1734:
1730:
1726:
1719:
1716:
1711:
1707:
1703:
1699:
1695:
1691:
1687:
1683:
1679:
1675:
1674:
1669:
1663:
1660:
1655:
1654:
1646:
1644:
1640:
1634:
1630:
1629:
1628:Combinatorica
1624:
1620:
1616:
1612:
1608:
1604:
1600:
1596:
1592:
1587:
1586:
1582:
1580:
1578:
1570:
1568:
1566:
1565:
1560:
1559:
1554:
1553:
1548:
1543:
1541:
1540:public domain
1536:
1532:
1530:
1525:
1522:
1517:
1514:
1509:
1505:
1501:
1497:
1493:
1489:
1485:
1484:Ronald Rivest
1481:
1476:
1473:
1469:
1465:
1461:
1457:
1453:
1445:
1443:
1429:
1407:
1403:
1399:
1394:
1390:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1321:
1318:
1315:
1310:
1306:
1300:
1293:
1289:
1285:
1280:
1276:
1272:
1269:
1253:
1249:
1245:
1240:
1236:
1217:
1216:
1215:
1208:
1201:
1194:
1189:
1185:
1181:
1177:
1173:
1169:
1164:
1163:
1161:
1145:
1142:
1139:
1133:
1110:
1106:
1102:
1099:
1094:
1090:
1081:
1078:
1075:
1071:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1024:
1021:
1018:
1013:
1003:
999:
981:
971:
967:
959:
953:
948:
944:
940:
931:
928:
922:
914:
910:
906:
891:
888:
883:
879:
871:
852:
848:
844:
841:
833:
829:
807:
802:
799:
791:
786:
783:
778:
774:
768:
764:
752:
748:
721:
716:
712:
708:
705:
702:
697:
692:
688:
681:
678:
670:
666:
642:
638:
634:
631:
628:
620:
616:
606:
605:not satisfied
603:
600:
583:
577:
562:
543:
539:
528:
526:
522:
518:
514:
507:
502:
489:
485:
481:
478:
477:
473:
470:
464:
461:
456:The algorithm
455:
453:
451:
447:
443:
438:
436:
432:
413:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
375:
371:
365:
361:
354:
347:
346:
345:
328:
323:
319:
312:
289:
283:
260:
255:
251:
244:
236:
232:
213:
207:
204:
201:
193:
189:
182:
159:
153:
130:
125:
121:
115:
111:
104:
84:
76:
60:
51:
49:
45:
41:
37:
33:
29:
19:
3125:Local search
3071:EdmondsâKarp
3027:BellmanâFord
2856:
2797:minimization
2629:GaussâNewton
2579:QuasiâNewton
2564:Trust region
2472:Optimization
2430:
2425:
2416:
2406:
2401:
2392:
2383:
2372:. Retrieved
2368:the original
2354:
2329:
2323:
2312:. Retrieved
2305:
2296:
2287:
2277:
2265:. Retrieved
2258:the original
2253:
2240:
2215:
2211:
2201:
2182:
2178:
2165:
2156:
2147:
2143:
2102:
2098:
2091:
2080:
2069:
2059:
2049:
2039:, retrieved
2033:
2027:
2002:
1999:Algorithmica
1998:
1982:
1957:
1951:
1942:
1933:
1923:
1913:
1904:
1895:
1870:
1864:
1839:
1833:
1811:(3): 20â36.
1808:
1804:
1798:
1773:
1769:
1763:
1728:
1718:
1677:
1671:
1662:
1652:
1632:
1626:
1598:
1594:
1574:
1571:Applications
1562:
1556:
1550:
1544:
1537:
1533:
1518:
1498:, including
1477:
1449:
1381:
1213:
1192:
1183:
1179:
1175:
1171:
1159:
912:
908:
904:
869:
604:
601:
598:
560:
510:
505:
499:0 < γ †1
496:
487:
483:
471:
468:
459:
446:feasible set
439:
428:
234:
230:
74:
53:Denoting by
52:
27:
26:
3145:Tabu search
2556:Convergence
2527:Line search
2218:(3): 7â19.
1680:(2): 4â10.
1500:Philip Gill
479:subject to
3177:Categories
2976:algorithms
2484:heuristics
2476:Algorithms
2374:2008-06-27
2314:2019-06-11
2267:30 January
2150:: 214â223.
2041:2016-06-01
1746:0897911334
1583:References
1264:subject to
1168:assignment
521:projective
448:as in the
2931:Paradigms
2830:quadratic
2547:Gradients
2509:Functions
2310:. AP News
2185:: 39â56.
1710:123541868
1694:0343-6993
1492:prior art
1351:…
1301:≤
1137:←
1103:α
1087:←
1041:…
941:−
932:⋅
929:γ
926:←
923:α
889:≥
842:−
839:←
800:−
784:−
758:←
706:…
682:
676:←
632:−
626:←
581:←
506:Algorithm
466:maximize
405:
399:
393:⋅
387:
381:⋅
32:algorithm
3162:Software
3039:Dijkstra
2870:exchange
2668:Hessians
2634:Gradient
2346:60450719
2232:18548851
2119:18899771
1825:42071587
1755:13101261
1615:12851754
1577:Gulf War
1529:Pentagon
1464:AT&T
1230:maximize
1174:←
599:do while
233:is in O(
3005:Kruskal
2995:BorĆŻvka
2985:Minimum
2722:General
2480:methods
2429:Accord
1974:1097868
1918:(1992).
1887:1097865
1856:1097880
1790:7257867
1702:0883185
1202:Example
1180:largest
1172:largest
2867:Basis-
2825:Linear
2795:Convex
2639:Mirror
2596:L-BFGS
2482:, and
2344:
2230:
2117:
2054:1986).
2019:779577
2017:
1972:
1928:1992).
1885:
1854:
1823:
1788:
1753:
1743:
1708:
1700:
1692:
1631:, Vol
1613:
1521:vector
1193:return
1160:end do
913:end if
909:return
565:γ
525:Soviet
429:using
46:. The
30:is an
3066:Dinic
2974:Graph
2342:S2CID
2261:(PDF)
2250:(PDF)
2228:S2CID
2175:(PDF)
2140:(PDF)
2115:S2CID
2015:S2CID
1995:(PDF)
1821:S2CID
1786:S2CID
1751:S2CID
1706:S2CID
1611:S2CID
433:(see
3032:SPFA
3000:Prim
2594:and
2364:FFII
2269:2016
1741:ISBN
1690:ISSN
1545:The
1363:1.0.
1184:item
1176:item
1019:<
905:then
679:diag
2962:cut
2827:and
2334:doi
2220:doi
2187:doi
2107:doi
2007:doi
1962:doi
1875:doi
1844:doi
1813:doi
1778:doi
1733:doi
1682:doi
1625:",
1603:doi
1488:RSA
1452:IBM
1357:0.9
1345:0.2
1339:0.1
1333:0.0
935:min
437:).
402:log
396:log
384:log
366:3.5
256:3.5
116:1.5
3179::
2478:,
2474::
2362:.
2340:.
2304:.
2286:.
2252:.
2226:.
2216:68
2214:.
2183:42
2181:.
2177:.
2148:16
2146:.
2142:.
2127:^
2113:.
2103:36
2101:.
2068:.
2013:.
2001:.
1997:.
1970:MR
1968:.
1883:MR
1881:.
1852:MR
1850:.
1819:.
1809:68
1807:.
1784:.
1772:.
1749:.
1739:.
1727:.
1704:.
1698:MR
1696:.
1688:.
1676:.
1642:^
1609:.
1599:44
1597:.
1579:.
1542:.
1531:.
870:if
567:.
563:,
491:.
486:â€
484:Ax
2960:/
2464:e
2457:t
2450:v
2377:.
2348:.
2336::
2317:.
2290:.
2271:.
2234:.
2222::
2195:.
2189::
2121:.
2109::
2074:.
2021:.
2009::
2003:1
1976:.
1964::
1889:.
1877::
1858:.
1846::
1827:.
1815::
1792:.
1780::
1774:4
1757:.
1735::
1712:.
1684::
1678:9
1656:.
1633:4
1617:.
1605::
1430:p
1408:2
1404:x
1400:,
1395:1
1391:x
1360:,
1354:,
1348:,
1342:,
1336:,
1330:=
1327:p
1322:,
1319:1
1316:+
1311:2
1307:p
1294:2
1290:x
1286:+
1281:1
1277:x
1273:p
1270:2
1254:2
1250:x
1246:+
1241:1
1237:x
1191:"
1186:.
1146:1
1143:+
1140:k
1134:k
1111:x
1107:h
1100:+
1095:k
1091:x
1082:1
1079:+
1076:k
1072:x
1050:}
1047:m
1044:,
1038:,
1035:1
1032:=
1029:i
1025:,
1022:0
1014:i
1010:)
1004:v
1000:h
996:(
990:|
982:i
978:)
972:v
968:h
964:(
960:/
954:k
949:i
945:v
938:{
892:0
884:v
880:h
853:x
849:h
845:A
834:v
830:h
808:c
803:1
796:)
792:A
787:2
779:v
775:D
769:T
765:A
761:(
753:x
749:h
727:)
722:k
717:m
713:v
709:,
703:,
698:k
693:1
689:v
685:(
671:v
667:D
643:k
639:x
635:A
629:b
621:k
617:v
584:0
578:k
558:,
544:0
540:x
488:b
472:x
469:c
414:,
411:)
408:L
390:L
376:2
372:L
362:n
358:(
355:O
332:)
329:L
324:4
320:n
316:(
313:O
293:)
290:L
287:(
284:O
264:)
261:L
252:n
248:(
245:O
235:n
231:m
217:)
214:L
211:)
208:m
205:+
202:n
199:(
194:3
190:n
186:(
183:O
163:)
160:L
157:(
154:O
134:)
131:L
126:2
122:n
112:m
108:(
105:O
85:L
75:m
61:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
