266:. These problems are represented by a number of linear constraints involving a number of variables. The previous method of solving these problems consisted of considering the problem as a high-dimensional solid with vertices, where the solution was approached by traversing from vertex to vertex. Karmarkar's novel method approaches the solution by cutting through the above solid in its traversal. Consequently, complex optimization problems are solved much faster using the Karmarkar's algorithm. A practical example of this efficiency is the solution to a complex problem in communications network optimization, where the solution time was reduced from weeks to days. His algorithm thus enables faster business and policy decisions. Karmarkar's algorithm has stimulated the development of several
230:. Karmarkar was a post-doctoral research fellow at IBM research (1983), Member of Technical Staff and fellow at Mathematical Sciences Research Center, AT&T Bell Laboratories (1983–1998), professor of mathematics at M.I.T. (1991), at Institute for Advanced study, Princeton (1996), and Homi Bhabha Chair Professor at the
238:
from 1998 to 2005. He was the scientific advisor to the chairman of the TATA group (2006–2007). During this time, he was funded by Ratan Tata to scale-up the supercomputer he had designed and prototyped at TIFR. The scaled-up model ranked ahead of supercomputer in Japan at that time and achieved the
517:
Amruter, B. S., Joshi, R., Karmarkar, N. K. "A Projective
Geometry Architecture for Scientific Computation". Proceedings of International Conference on Application Specific Array Processors, IEEE Computer Society, p. 6480
239:
best ranking India ever achieved in supercomputing. He was the founding director of
Computational Research labs in Pune, where the scaling-up work was performed. He continues to work on his new architecture for supercomputing.
319:
in 2000 for his work on polynomial-time interior-point methods for linear programming for "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing".
527:
Karmarkar, N. K. "A New
Parallel Architecture for Scientific Computation Based on Finite Projective Geometries". Proceeding of Mathematical Programming, State of the Art, p. 136148 (1994).
186:, which is generally referred to as an interior point method. The algorithm is a cornerstone in the field of linear programming. He published his famous result in 1984 while he was working for
508:
Karmarkar, N. K., Ramakrishnan, K. G. "Computational results of an interior point algorithm for large scale linear programming". Mathematical
Programming. 52: 555–586 (1991).
406:
622:
829:
1024:
1014:
947:
943:
757:
1029:
1044:
891:
994:
989:
1034:
979:
615:
579:
1039:
585:
365:
231:
1004:
64:
410:
999:
608:
312:
361:
223:
215:
82:
73:
1009:
725:
339:
545:
559:
485:
452:
392:
335:
600:
1049:
465:
984:
328:
Distinguished
Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993).
176:
537:
1019:
432:
17:
253:
172:
97:
466:"A new parallel architecture for sparse matrix computation based on finite projective geometries"
974:
632:
355:
316:
322:
Srinivasa
Ramanujan Birth Centenary Award for 1999, presented by the Prime Minister of India.
283:
279:
267:
969:
903:
833:
8:
691:
591:
295:
753:
491:
259:
183:
733:
481:
211:
187:
118:
867:
777:
729:
687:
683:
647:
495:
473:
151:
470:
Proceedings of the 1991 ACM/IEEE conference on
Supercomputing – Supercomputing '91
939:
877:
797:
787:
747:
737:
719:
643:
331:
291:
263:
227:
156:
925:
819:
783:
771:
697:
669:
651:
287:
270:, some of which are used in current implementations of linear-program solvers.
52:
963:
933:
921:
895:
885:
861:
815:
803:
793:
765:
701:
679:
630:
448:
388:
299:
929:
881:
845:
839:
713:
655:
477:
325:
Distinguished
Alumnus Award, Indian Institute of Technology, Bombay, 1996.
899:
823:
809:
761:
743:
114:
917:
913:
673:
663:
659:
207:
191:
907:
873:
855:
851:
182:
He invented one of the first provably polynomial time algorithms for
128:
368:
for the Best
Published Contributions to Operations Research (1984).
171:(born circa 1956) is an Indian mathematician. Karmarkar developed
48:
595:
235:
203:
135:
538:"Golden Plate Awardees of the American Academy of Achievement"
438:. California Institute of Technology. 8 June 1979. p. 13.
77:
68:
586:
Flashback: An
Interior Point Method for Linear Programming
219:
86:
407:"Karmarkar, Narendra K., ISI Highly Cited Researchers"
371:
President of India gold medal, I.I.T. Bombay (1978).
351:
Marconi International Young Scientist Award (1985).
961:
616:
334:in Discrete Mathematics given jointly by the
358:, presented by former U.S. president (1985).
633:Paris Kanellakis Theory and Practice Award
623:
609:
1025:California Institute of Technology alumni
1015:University of California, Berkeley alumni
463:
348:Texas Instruments Founders' Prize (1986).
345:Fellow of Bell Laboratories (since 1987).
247:
560:"Whiz kids rub elbows with right stuff"
404:
14:
962:
366:Operations Research Society of America
232:Tata Institute of Fundamental Research
1030:Indian emigrants to the United States
604:
1045:American academics of Indian descent
565:. Rocky Mountain News. 30 June 1985.
313:Association for Computing Machinery
24:
995:21st-century Indian mathematicians
990:20th-century Indian mathematicians
433:"Eighty-Fifth Annual Commencement"
273:
224:University of California, Berkeley
216:California Institute of Technology
83:University of California, Berkeley
74:California Institute of Technology
25:
1061:
573:
382:
226:in 1983 under the supervision of
340:Mathematical Programming Society
27:Indian mathematician (born 1956)
1035:American operations researchers
980:Theoretical computer scientists
552:
546:American Academy of Achievement
356:American Academy of Achievement
206:in Electrical Engineering from
530:
521:
511:
502:
457:
442:
425:
398:
13:
1:
1040:Indian operations researchers
453:Mathematics Genealogy Project
393:Mathematics Genealogy Project
375:
362:Frederick W. Lanchester Prize
336:American Mathematical Society
258:Karmarkar's algorithm solves
222:in Computer Science from the
141:Coping with NP-Hard Problems
1005:American computer scientists
464:Karmarkar, Narendra (1991).
315:awarded him the prestigious
282:, Karmarkar worked on a new
197:
7:
177:ISI highly cited researcher
45:1956 (age 67–68)
10:
1066:
1000:Indian computer scientists
580:Distinguished Alumnus 1996
354:Golden Plate Award of the
251:
169:Narendra Krishna Karmarkar
36:Narendra Krishna Karmarkar
639:
305:
290:, based on concepts from
162:
150:
134:
124:
110:
103:
93:
60:
41:
34:
588:IIT Bombay Heritage Fund
1010:Scientists at Bell Labs
242:
202:Karmarkar received his
317:Paris Kanellakis Award
268:interior-point methods
478:10.1145/125826.126029
280:interior-point method
278:After working on the
254:Karmarkar's algorithm
248:Karmarkar's algorithm
175:. He is listed as an
173:Karmarkar's algorithm
98:Karmarkar's algorithm
472:. pp. 358–369.
1050:People from Gwalior
542:www.achievement.org
296:projective geometry
985:Numerical analysts
592:Karmarkar function
449:Narendra Karmarkar
389:Narendra Karmarkar
260:linear programming
184:linear programming
1020:IIT Bombay alumni
957:
956:
188:Bell Laboratories
166:
165:
119:computing science
105:Scientific career
16:(Redirected from
1057:
625:
618:
611:
602:
601:
567:
566:
564:
556:
550:
549:
534:
528:
525:
519:
515:
509:
506:
500:
499:
461:
455:
446:
440:
439:
437:
429:
423:
422:
420:
418:
413:on 23 March 2006
409:. Archived from
402:
396:
386:
152:Doctoral advisor
146:
32:
31:
21:
1065:
1064:
1060:
1059:
1058:
1056:
1055:
1054:
960:
959:
958:
953:
635:
631:Winners of the
629:
576:
571:
570:
562:
558:
557:
553:
536:
535:
531:
526:
522:
516:
512:
507:
503:
488:
462:
458:
447:
443:
435:
431:
430:
426:
416:
414:
403:
399:
387:
383:
378:
332:Fulkerson Prize
308:
292:finite geometry
276:
274:Galois geometry
264:polynomial time
256:
250:
245:
228:Richard M. Karp
200:
157:Richard M. Karp
144:
81:
72:
61:Alma mater
56:
46:
37:
28:
23:
22:
15:
12:
11:
5:
1063:
1053:
1052:
1047:
1042:
1037:
1032:
1027:
1022:
1017:
1012:
1007:
1002:
997:
992:
987:
982:
977:
972:
955:
954:
952:
951:
937:
911:
889:
871:
865:
859:
849:
843:
837:
827:
813:
807:
801:
791:
781:
775:
769:
751:
741:
723:
717:
711:
705:
695:
677:
667:
640:
637:
636:
628:
627:
620:
613:
605:
599:
598:
589:
583:
575:
574:External links
572:
569:
568:
551:
529:
520:
510:
501:
486:
456:
441:
424:
397:
380:
379:
377:
374:
373:
372:
369:
359:
352:
349:
346:
343:
329:
326:
323:
320:
307:
304:
288:supercomputing
275:
272:
252:Main article:
249:
246:
244:
241:
199:
196:
164:
163:
160:
159:
154:
148:
147:
138:
132:
131:
126:
122:
121:
112:
108:
107:
101:
100:
95:
94:Known for
91:
90:
62:
58:
57:
53:Madhya Pradesh
47:
43:
39:
38:
35:
26:
9:
6:
4:
3:
2:
1062:
1051:
1048:
1046:
1043:
1041:
1038:
1036:
1033:
1031:
1028:
1026:
1023:
1021:
1018:
1016:
1013:
1011:
1008:
1006:
1003:
1001:
998:
996:
993:
991:
988:
986:
983:
981:
978:
976:
975:Living people
973:
971:
968:
967:
965:
949:
945:
941:
938:
935:
931:
927:
923:
919:
915:
912:
909:
905:
901:
897:
893:
890:
887:
883:
879:
875:
872:
869:
866:
863:
860:
857:
853:
850:
847:
844:
841:
838:
835:
831:
828:
825:
821:
817:
814:
811:
808:
805:
802:
799:
795:
792:
789:
785:
782:
779:
776:
773:
770:
767:
763:
759:
755:
752:
749:
745:
742:
739:
735:
731:
727:
724:
721:
718:
715:
712:
709:
706:
703:
699:
696:
693:
689:
685:
681:
678:
675:
671:
668:
665:
661:
657:
653:
649:
645:
642:
641:
638:
634:
626:
621:
619:
614:
612:
607:
606:
603:
597:
593:
590:
587:
584:
581:
578:
577:
561:
555:
547:
543:
539:
533:
524:
514:
505:
497:
493:
489:
483:
479:
475:
471:
467:
460:
454:
450:
445:
434:
428:
412:
408:
405:Thomson ISI.
401:
394:
390:
385:
381:
370:
367:
363:
360:
357:
353:
350:
347:
344:
341:
337:
333:
330:
327:
324:
321:
318:
314:
310:
309:
303:
301:
300:finite fields
297:
294:, especially
293:
289:
285:
281:
271:
269:
265:
261:
255:
240:
237:
233:
229:
225:
221:
218:in 1979, and
217:
213:
209:
205:
195:
193:
189:
185:
180:
178:
174:
170:
161:
158:
155:
153:
149:
142:
139:
137:
133:
130:
127:
123:
120:
116:
113:
109:
106:
102:
99:
96:
92:
88:
84:
79:
75:
70:
66:
63:
59:
54:
50:
44:
40:
33:
30:
19:
904:Mitzenmacher
707:
554:
541:
532:
523:
513:
504:
469:
459:
444:
427:
415:. Retrieved
411:the original
400:
384:
284:architecture
277:
262:problems in
257:
201:
181:
168:
167:
140:
125:Institutions
104:
29:
970:1957 births
115:Mathematics
964:Categories
778:Buchberger
582:IIT Bombay
487:0897914597
376:References
208:IIT Bombay
192:New Jersey
65:IIT Bombay
944:Ferragina
834:Leiserson
720:Franaszek
708:Karmarkar
214:from the
210:in 1978,
198:Biography
129:Bell Labs
18:Karmarkar
926:McSherry
820:Charikar
804:Mehlhorn
754:Holzmann
748:Schapire
738:Strassen
692:McMillan
948:Manzini
940:Burrows
886:Szegedy
878:Gibbons
868:Pevzner
862:Shenker
830:Blumofe
798:Rogaway
794:Bellare
772:Brayton
758:Kurshan
734:Solovay
698:Sleator
688:Emerson
652:Hellman
644:Adleman
518:(1992).
496:6665759
451:at the
417:20 June
391:at the
364:of the
55:, India
49:Gwalior
950:(2022)
936:(2021)
930:Nissim
910:(2020)
900:Karlin
896:Broder
888:(2019)
882:Matias
870:(2018)
864:(2017)
858:(2016)
848:(2015)
842:(2014)
840:Demmel
836:(2013)
826:(2012)
816:Broder
812:(2011)
806:(2010)
800:(2009)
790:(2008)
788:Vapnik
784:Cortes
780:(2007)
774:(2006)
768:(2005)
766:Wolper
750:(2004)
744:Freund
740:(2003)
726:Miller
722:(2002)
716:(2001)
710:(2000)
704:(1999)
702:Tarjan
694:(1998)
684:Clarke
680:Bryant
676:(1997)
670:Lempel
666:(1996)
664:Shamir
660:Rivest
656:Merkle
648:Diffie
596:Scilab
494:
484:
342:(1988)
338:&
306:Awards
236:Mumbai
204:B.Tech
145:(1983)
143:
136:Thesis
111:Fields
934:Smith
922:Dwork
918:Dinur
908:Upfal
824:Indyk
810:Samet
762:Vardi
730:Rabin
714:Myers
563:(PDF)
492:S2CID
436:(PDF)
298:over
220:Ph.D.
69:BTech
914:Blum
892:Azar
874:Alon
856:Naor
852:Fiat
846:Luby
482:ISBN
419:2009
311:The
286:for
243:Work
212:M.S.
42:Born
674:Ziv
594:in
474:doi
234:in
190:in
87:PhD
966::
946:,
942:,
932:,
928:,
924:,
920:,
916:,
906:,
902:,
898:,
894:,
884:,
880:,
876:,
854:,
832:,
822:,
818:,
796:,
786:,
764:,
760:,
756:,
746:,
736:,
732:,
728:,
700:,
690:,
686:,
682:,
672:,
662:,
658:,
654:,
650:,
646:,
544:.
540:.
490:.
480:.
468:.
302:.
194:.
179:.
117:,
78:MS
51:,
624:e
617:t
610:v
548:.
498:.
476::
421:.
395:.
89:)
85:(
80:)
76:(
71:)
67:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.