327:
can be implemented in polynomial time. The paper was translated into several languages and spread around the world unusually quickly. Authors of a 1981 survey of his work noted that it "has caused great excitement and stimulated a flood of technical papers" and was covered by major newspapers. It was
353:
noted that the method was not practical, "but it was a real breakthrough for the world of operations research and computer science, since it proved that the design of polynomial time algorithms for linear programming was possible and in fact opened the way to other, more practical, algorithms that
426:
Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems." He was called one of the world's most famous computer scientists at the time of his death by Haym Hirsh, chair of the computer science department at
Rutgers. "Computer
379:
described him as "selfless, open, patient, sympathetic, understanding, considerate." Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity."
1424:
433:
obituary. Bahman
Kalantari, a friend and colleague at Rutgers, wrote: "Surely, Khachiyan shall always remain to be among the greatest and most legendary figures in the field of mathematical programming."
1294:
336:
in 1981. It was Gács and Lovász who first brought attention to
Khachiyan's paper at the International Symposium on Mathematical Programming in Montreal in August 1979. It was further popularized when
290:. In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems." Khachiyan immigrated to the United States in 1989. He first taught at
1419:
1239:"I had such a shambolic, dysfunctional upbringing my parents didn't even bother to teach me chess — unheard of and frankly shameful for Russian family of Armenian and Ashkenazi origins lol!"
1464:
931:
306:
at
Rutgers in 1992. By 2005, he held the position of Professor II at Rutgers, reserved for those faculty who have achieved scholarly eminence in their discipline.
1459:
1211:
807:
1399:
1394:
756:"Family portrait of Armenian ancestors, Nagorno-Karabakh, 1920s (great great grandparents in the center, grandmother little girl on the left with the pigtails)"
1404:
1308:
1125:
1434:
287:
251:
497:
561:
372:
profile of him described
Khachiyan as "a relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school."
1409:
1013:
876:
701:
423:
for outstanding papers in the area of discrete mathematics, particularly his 1979 article "A polynomial algorithm in linear programming."
605:
1454:
1449:
1429:
1414:
1276:
1246:
1105:
763:
42:
1093:
416:
996:
Gács, Peter; Lovász, Laszlo (1981). "Khachiyan's algorithm for linear programming". In König, H.; Korte, B.; Ritter, K. (eds.).
1097:
1444:
1215:
1354:
966:
939:
420:
384:
1173:
725:
279:
263:
134:
1469:
1341:
400:
85:
984:
Zhurnal
Vychisditel'noi Matematiki i Matematicheskoi Fiziki (USSR Computational Mathematics and Mathematical Physics)
1268:
902:
896:
687:
1439:
1144:
255:
836:
328:
originally published without proofs, which were provided by
Khachiyan in a later paper published in 1980 and by
349:
Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."
259:
1334:
1132:
811:
871:
235:
1090:
The Making of a New
Science: A Personal Journey Through the Early Years of Theoretical Computer Science
278:
Khachiyan began his career at the Soviet
Academy of Sciences, working as a researcher at the academy's
1348:
366:. Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand." A 1979
1389:
1384:
1328:
1164:
1043:
531:
376:
211:
1126:"My Memories of Leonid Khachiyan and a Personal Tribute for His Contributions in Linear Programming"
882:
816:
231:
215:
866:
1136:
1059:
1034:
958:
691:
642:
610:
566:
502:
324:
295:
291:
199:
188:
138:
329:
1365:
1238:
755:
1101:
1067:
1009:
841:
522:
363:
342:
283:
1304:
1299:
1182:
1085:
1051:
1001:
948:
734:
634:
539:
350:
333:
320:
303:
267:
210:
running time. Even though this algorithm was shown to be impractical, it has inspired other
195:
180:
156:
187:; May 3, 1952 – April 29, 2005) was a Soviet and American mathematician and
927:
923:
412:
207:
116:
1047:
535:
1358:
638:
557:
517:
429:
392:
388:
368:
239:
106:
427:
scientists and mathematicians say his work helped revolutionize his field," noted his
1378:
1140:
646:
543:
319:
Khachiyan is best known for his four-page
February 1979 paper that indicated how an
396:
1055:
246:
Armenians. He had two brothers: Boris and Yevgeniy (Eugene). His family moved to
1203:
1029:
337:
41:
17:
1187:
1168:
798:
Todd, Michael (October 2005). "Leonid Khachiyan, 1952–2005: An Appreciation".
739:
720:
227:
203:
66:
1071:
953:
243:
1280:
1242:
1063:
1005:
894:
Khachiyan, L. G. 1979. "A Polynomial Algorithm in Linear Programming".
759:
695:
234:
parents Genrikh Borisovich Khachiyan, a mathematician and professor of
982:
Khachiyan, L. G. 1980. "Polynomial Algorithms in Linear Programming".
962:
299:
247:
1032:(November 2, 1979). "Mathematicians Amazed by Russian's Discovery".
625:
Lawler, Eugene L. (1980). "The Great Mathematical Sputnik of 1979".
391:
and Nina, who were teenagers at the time of his death. He became a
1000:. Mathematical Programming Studies. Vol. 14. pp. 61–68.
688:"World Renowned Computer Scientist Leonid G. Khachiyan Dies at 52"
250:
in 1961, when he was nine. He received a master's degree from the
375:
He was known as "Leo" and "Lenya" to his friends and colleagues.
1425:
Academic staff of the Moscow Institute of Physics and Technology
1324:
171:
168:
165:
162:
837:"Leonid Khachiyan, 52; Computer Science Expert at Rutgers"
218:
and is considered a significant theoretical breakthrough.
1337:
from the Computer Science Department, Rutgers University.
1295:"Leonid Khachiyan, professor, leading computer scientist"
606:"Leonid Khachiyan Is Dead at 52; Advanced Computer Math"
27:
Soviet and American mathematician and computer scientist
1204:"SIAM: Leonid Khachiyan, 1952 - 2005: An Appreciation"
159:
520:(30 November 1979). "Linear Programming Discovery".
130:
112:
101:
93:
74:
48:
32:
1420:Moscow Institute of Physics and Technology alumni
264:Computer Center of the Soviet Academy of Sciences
135:Computer Center of the Soviet Academy of Sciences
562:"A Soviet Discovery Rocks World of Mathematics"
383:Khachiyan married Olga Pischikova Reynberg, of
1212:Society for Industrial and Applied Mathematics
694:Department of Computer Science. Archived from
491:
489:
487:
485:
483:
481:
479:
455:His last name was often spelled in English as
918:
916:
914:
912:
362:Khachiyan spoke Russian and English, but not
8:
1342:Leonid Khachiyan, 1952–2005: An Appreciation
1119:
1117:
793:
791:
789:
787:
785:
783:
781:
294:as a visiting professor. In 1990 he joined
1159:
1157:
831:
829:
827:
682:
680:
678:
676:
599:
597:
288:Moscow Institute of Physics and Technology
252:Moscow Institute of Physics and Technology
40:
29:
1465:Naturalized citizens of the United States
1186:
952:
815:
738:
714:
712:
710:
674:
672:
670:
668:
666:
664:
662:
660:
658:
656:
595:
593:
591:
589:
587:
585:
583:
581:
579:
577:
498:"Soviet Mathematician Is Obscure No More"
387:origin, in 1985. They had two daughters,
411:In 1982 he was awarded the prestigious
998:Mathematical Programming at Oberwolfach
865:Madden, Andrew P. (September 1, 2005).
496:Whitney, Craig R. (November 27, 1979).
475:
448:
354:were designed in the following years."
860:
858:
856:
854:
852:
226:Khachiyan was born on May 3, 1952, in
1460:Soviet emigrants to the United States
877:Massachusetts Institute of Technology
810:Activity Group on Optimization: 4–6.
403:on April 29, 2005, at the age of 52.
7:
1400:21st-century American mathematicians
1395:20th-century American mathematicians
1237:Khachiyan, Anna (December 4, 2019).
1218:from the original on 21 January 2021
1202:Todd, Michael J. (1 December 2005).
1405:American people of Armenian descent
1249:from the original on 17 August 2020
766:from the original on 17 August 2020
395:U.S. citizen in 2000. He died of a
298:as a visiting professor. He became
238:, and Zhanna Saakovna Khachiyan, a
1435:Russian people of Armenian descent
754:Khachiyan, Anna (April 25, 2020).
639:10.1002/j.2326-1951.1980.tb01345.x
25:
1277:Mathematical Optimization Society
719:Gurvich, Vladimir (6 June 2008).
254:. In 1978 he earned his Ph.D. in
932:"The Ellipsoid Method: A Survey"
417:Mathematical Programming Society
282:in Moscow. He also worked as an
155:
604:Pearce, Jeremy (May 22, 2005).
544:10.1126/science.206.4422.1022-c
1347:Discrete Applied Mathematics:
1307:). May 5, 2005. Archived from
900:244, 1093-1096 (translated in
1:
1355:Mathematics Genealogy Project
1335:In Memoriam: Leonid Khachiyan
421:American Mathematical Society
151:Leonid Genrikhovich Khachiyan
53:Leonid Genrikhovich Khachiyan
1410:American computer scientists
1174:Discrete Applied Mathematics
1056:10.1126/science.206.4418.545
726:Discrete Applied Mathematics
1169:"Remembering Leo Khachiyan"
930:; Todd, Michael J. (1981).
401:South Brunswick, New Jersey
270:from the same institution.
202:, which was the first such
194:He was most famous for his
185:Леони́д Ге́нрихович Хачия́н
97:Soviet Union, United States
86:South Brunswick, New Jersey
1486:
1455:Soviet computer scientists
1450:Rutgers University faculty
1430:Mathematicians from Moscow
1415:Cornell University faculty
1124:Kalantari, Bahman (2005).
903:Soviet Mathematics Doklady
897:Doklady Akademii Nauk SSSR
310:Work on linear programming
1349:Remembering Leo Khachiyan
1188:10.1016/j.dam.2007.08.001
740:10.1016/j.dam.2008.04.013
256:computational mathematics
184:
144:
123:
39:
242:. His grandparents were
222:Early life and education
867:"Obituary: Mystery Man"
800:SIAG/OPT Views-and-News
358:Personal life and death
266:and in 1984 a D.Sc. in
260:theoretical mathematics
1364:New York Times :
1133:Allen Institute for AI
954:10.1287/opre.29.6.1039
461:Leonid Henry Khachiyan
1445:Soviet mathematicians
1269:"The Fulkerson Prize"
872:MIT Technology Review
346:on November 2, 1979.
236:theoretical mechanics
212:randomized algorithms
1311:on 4 September 2017.
1283:on 12 February 2019.
560:(November 7, 1979).
1048:1979Sci...206..545B
940:Operations Research
906:20, 191-194, 1979).
536:1979Sci...206.1022B
196:ellipsoid algorithm
1470:Russian scientists
1006:10.1007/BFb0120921
692:Rutgers University
611:The New York Times
567:The New York Times
558:Browne, Malcolm W.
503:The New York Times
325:linear programming
296:Rutgers University
292:Cornell University
216:convex programming
200:linear programming
189:computer scientist
139:Rutgers University
1181:(11): 1961–1962.
1086:Ausiello, Giorgio
1042:(4418): 545–546.
1030:Kolata, Gina Bari
1015:978-3-642-00805-4
842:Los Angeles Times
733:(11): 1957–1960.
284:adjunct professor
148:
147:
125:Scientific career
16:(Redirected from
1477:
1440:Soviet Armenians
1359:Leonid Khachiyan
1329:Leonid Khachiyan
1313:
1312:
1305:Associated Press
1300:The Boston Globe
1291:
1285:
1284:
1279:. Archived from
1265:
1259:
1258:
1256:
1254:
1234:
1228:
1227:
1225:
1223:
1210:. Philadelphia:
1208:archive.siam.org
1199:
1193:
1192:
1190:
1161:
1152:
1151:
1149:
1143:. Archived from
1130:
1121:
1112:
1111:
1082:
1076:
1075:
1026:
1020:
1019:
993:
987:
980:
974:
973:
971:
965:. Archived from
956:
947:(6): 1039–1091.
936:
928:Goldfarb, Donald
924:Bland, Robert G.
920:
907:
892:
886:
880:
862:
847:
846:
833:
822:
821:
819:
795:
776:
775:
773:
771:
751:
745:
744:
742:
716:
705:
699:
684:
651:
650:
622:
616:
615:
601:
572:
571:
554:
548:
547:
514:
508:
507:
493:
464:
459:. Anglicized as
453:
351:Giorgio Ausiello
343:Science Magazine
321:ellipsoid method
315:Ellipsoid method
304:computer science
268:computer science
206:known to have a
186:
178:
177:
174:
173:
170:
167:
164:
161:
81:
62:
60:
44:
34:Leonid Khachiyan
30:
21:
1485:
1484:
1480:
1479:
1478:
1476:
1475:
1474:
1375:
1374:
1372:
1321:
1316:
1293:
1292:
1288:
1267:
1266:
1262:
1252:
1250:
1236:
1235:
1231:
1221:
1219:
1201:
1200:
1196:
1167:(6 June 2008).
1165:Chvátal, Václav
1163:
1162:
1155:
1147:
1128:
1123:
1122:
1115:
1108:
1084:
1083:
1079:
1028:
1027:
1023:
1016:
995:
994:
990:
981:
977:
969:
934:
922:
921:
910:
893:
889:
864:
863:
850:
835:
834:
825:
817:10.1.1.131.3938
797:
796:
779:
769:
767:
753:
752:
748:
721:"Recalling Leo"
718:
717:
708:
686:
685:
654:
624:
623:
619:
603:
602:
575:
556:
555:
551:
518:Boas, Harold P.
516:
515:
511:
495:
494:
477:
468:
467:
454:
450:
440:
413:Fulkerson Prize
409:
360:
340:reported it in
317:
312:
280:Computer Center
276:
224:
158:
154:
137:
117:Fulkerson Prize
89:
83:
79:
70:
64:
58:
56:
55:
54:
35:
28:
23:
22:
18:L. G. Khachiyan
15:
12:
11:
5:
1483:
1481:
1473:
1472:
1467:
1462:
1457:
1452:
1447:
1442:
1437:
1432:
1427:
1422:
1417:
1412:
1407:
1402:
1397:
1392:
1387:
1377:
1376:
1370:
1369:
1362:
1351:
1345:
1338:
1332:
1320:
1319:External links
1317:
1315:
1314:
1286:
1260:
1229:
1194:
1153:
1150:on 2020-01-13.
1113:
1106:
1077:
1021:
1014:
988:
975:
972:on 2015-07-01.
908:
887:
848:
845:. May 5, 2005.
823:
777:
746:
706:
698:on 2016-09-11.
652:
617:
573:
549:
530:(4422): 1022.
509:
474:
473:
472:
466:
465:
447:
446:
445:
444:
439:
436:
430:New York Times
408:
405:
385:Russian-Jewish
377:Václav Chvátal
369:New York Times
359:
356:
316:
313:
311:
308:
275:
272:
240:civil engineer
223:
220:
146:
145:
142:
141:
132:
128:
127:
121:
120:
114:
110:
109:
103:
99:
98:
95:
91:
90:
84:
82:(aged 52)
78:April 29, 2005
76:
72:
71:
69:, Soviet Union
65:
52:
50:
46:
45:
37:
36:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1482:
1471:
1468:
1466:
1463:
1461:
1458:
1456:
1453:
1451:
1448:
1446:
1443:
1441:
1438:
1436:
1433:
1431:
1428:
1426:
1423:
1421:
1418:
1416:
1413:
1411:
1408:
1406:
1403:
1401:
1398:
1396:
1393:
1391:
1388:
1386:
1383:
1382:
1380:
1373:
1367:
1363:
1360:
1356:
1352:
1350:
1346:
1343:
1339:
1336:
1333:
1330:
1326:
1323:
1322:
1318:
1310:
1306:
1302:
1301:
1296:
1290:
1287:
1282:
1278:
1274:
1270:
1264:
1261:
1248:
1244:
1240:
1233:
1230:
1217:
1213:
1209:
1205:
1198:
1195:
1189:
1184:
1180:
1176:
1175:
1170:
1166:
1160:
1158:
1154:
1146:
1142:
1138:
1134:
1127:
1120:
1118:
1114:
1109:
1107:9783319626802
1103:
1099:
1095:
1091:
1087:
1081:
1078:
1073:
1069:
1065:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1036:
1031:
1025:
1022:
1017:
1011:
1007:
1003:
999:
992:
989:
985:
979:
976:
968:
964:
960:
955:
950:
946:
942:
941:
933:
929:
925:
919:
917:
915:
913:
909:
905:
904:
899:
898:
891:
888:
884:
878:
874:
873:
868:
861:
859:
857:
855:
853:
849:
844:
843:
838:
832:
830:
828:
824:
818:
813:
809:
805:
801:
794:
792:
790:
788:
786:
784:
782:
778:
765:
761:
757:
750:
747:
741:
736:
732:
728:
727:
722:
715:
713:
711:
707:
703:
697:
693:
689:
683:
681:
679:
677:
675:
673:
671:
669:
667:
665:
663:
661:
659:
657:
653:
648:
644:
640:
636:
632:
628:
621:
618:
613:
612:
607:
600:
598:
596:
594:
592:
590:
588:
586:
584:
582:
580:
578:
574:
569:
568:
563:
559:
553:
550:
545:
541:
537:
533:
529:
525:
524:
519:
513:
510:
505:
504:
499:
492:
490:
488:
486:
484:
482:
480:
476:
470:
469:
462:
458:
452:
449:
442:
441:
437:
435:
432:
431:
424:
422:
418:
414:
406:
404:
402:
398:
394:
390:
386:
381:
378:
373:
371:
370:
365:
357:
355:
352:
347:
345:
344:
339:
335:
334:Laszlo Lovász
331:
326:
322:
314:
309:
307:
305:
301:
297:
293:
289:
285:
281:
273:
271:
269:
265:
261:
257:
253:
249:
245:
241:
237:
233:
229:
221:
219:
217:
213:
209:
205:
201:
197:
192:
190:
182:
176:
152:
143:
140:
136:
133:
129:
126:
122:
118:
115:
111:
108:
105:2, including
104:
100:
96:
92:
87:
77:
73:
68:
51:
47:
43:
38:
31:
19:
1371:
1309:the original
1298:
1289:
1281:the original
1272:
1263:
1251:. Retrieved
1232:
1220:. Retrieved
1207:
1197:
1178:
1172:
1145:the original
1089:
1080:
1039:
1033:
1024:
997:
991:
983:
978:
967:the original
944:
938:
901:
895:
890:
883:archived PDF
870:
840:
803:
799:
768:. Retrieved
749:
730:
724:
702:archived PDF
696:the original
633:(7): 12–15.
630:
627:The Sciences
626:
620:
609:
565:
552:
527:
521:
512:
501:
460:
456:
451:
428:
425:
410:
397:heart attack
382:
374:
367:
361:
348:
341:
318:
277:
225:
193:
150:
149:
131:Institutions
124:
80:(2005-04-29)
1390:2005 deaths
1385:1952 births
1340:SIAM news:
1273:mathopt.org
407:Recognition
393:naturalized
338:Gina Kolata
198:(1979) for
94:Citizenship
63:May 3, 1952
1379:Categories
1096:. p.
986:20, 51-68.
438:References
330:Peter Gács
208:polynomial
59:1952-05-03
1253:17 August
812:CiteSeerX
770:17 August
471:Citations
300:professor
262:from the
228:Leningrad
204:algorithm
67:Leningrad
1366:Obituary
1247:Archived
1216:Archived
1141:15568389
1094:Springer
1088:(2018).
1072:17759415
764:Archived
647:56588045
457:Khachian
419:and the
364:Armenian
244:Karabakh
232:Armenian
102:Children
1303:. (via
1243:Twitter
1222:27 June
1064:1749236
1044:Bibcode
1035:Science
806:(1–2).
760:Twitter
532:Bibcode
523:Science
415:by the
286:at the
181:Russian
1139:
1104:
1070:
1062:
1012:
963:170362
961:
814:
645:
274:Career
248:Moscow
119:(1982)
113:Awards
88:, U.S.
1148:(PDF)
1137:S2CID
1129:(PDF)
1060:JSTOR
970:(PDF)
959:JSTOR
935:(PDF)
643:S2CID
443:Notes
1353:The
1325:DBLP
1255:2020
1224:2021
1102:ISBN
1068:PMID
1010:ISBN
808:SIAM
772:2020
389:Anna
332:and
323:for
214:for
107:Anna
75:Died
49:Born
1183:doi
1179:156
1098:174
1052:doi
1040:206
1002:doi
949:doi
735:doi
731:156
635:doi
540:doi
528:206
399:in
302:of
230:to
1381::
1357::
1327::
1297:.
1275:.
1271:.
1245:.
1241:.
1214:.
1206:.
1177:.
1171:.
1156:^
1135:.
1131:.
1116:^
1100:.
1092:.
1066:.
1058:.
1050:.
1038:.
1008:.
957:.
945:29
943:.
937:.
926:;
911:^
875:.
869:.
851:^
839:.
826:^
804:16
802:.
780:^
762:.
758:.
729:.
723:.
709:^
690:.
655:^
641:.
631:20
629:.
608:.
576:^
564:.
538:.
526:.
500:.
478:^
191:.
183::
179:;
172:ən
169:iː
166:tʃ
163:ɑː
1368:.
1361:.
1344:.
1331:.
1257:.
1226:.
1191:.
1185::
1110:.
1074:.
1054::
1046::
1018:.
1004::
951::
885:)
881:(
879:.
820:.
774:.
743:.
737::
704:)
700:(
649:.
637::
614:.
570:.
546:.
542::
534::
506:.
463:.
258:/
175:/
160:k
157:/
153:(
61:)
57:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
