31:
440:, an algorithm for finding maximum matchings in general graphs; the latter is still the most efficient known algorithm for the problem. With Mehta, Saberi, and Umesh Vazirani, he showed in 2007 how to formulate the problem of choosing advertisements for
483:
for "fundamental and sustained contributions to the design of algorithms, including approximation algorithms, computational complexity theory, and algorithmic game theory, central to operations research and the management sciences".
405:, championing the primal-dual schema, which he applied to problems arising in network design, facility location and web caching, and clustering. In July 2001 he published what is widely regarded as the definitive book on
1014:
1575:
603:
283:
409:(Springer-Verlag, Berlin). Since 2002, he has been at the forefront of the effort to understand the computability of market equilibria, with an extensive body of work on the topic.
1007:
1550:
809:
Jain, Kamal; Vazirani, Vijay V. (2001), "Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and
Lagrangian relaxation",
1555:
1570:
1000:
1595:
1615:
1590:
607:
1585:
1605:
1580:
933:
914:
710:
Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. (1986), "Random generation of combinatorial structures from a uniform distribution",
178:
1560:
469:
465:
351:
347:
315:
77:
855:
793:
758:
686:
669:
355:
287:
183:
36:
390:
371:
343:
173:
155:
417:
547:
1610:
1565:
1241:
1023:
528:
493:
480:
131:
433:
93:
1488:
1201:
1360:
539:
Three of his papers on the subject from that time period have over 100 citations each, according to Google scholar:
870:
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh; Vazirani, Vijay (2007), "AdWords and generalized online matching",
1600:
406:
402:
401:, and the equivalence between random generation and approximate counting. During the 1990s he worked mostly on
398:
1392:
1352:
379:
159:
1432:
1545:
1512:
1257:
1340:
1312:
1296:
667:; Vazirani, Umesh V.; Vazirani, Vijay V. (1990), "An optimal algorithm for on-line bipartite matching",
473:
126:
950:
1540:
1061:
303:
1384:
1380:
1189:
930:
911:
1480:
1344:
1336:
1320:
1428:
1516:
1476:
1280:
895:
834:
772:
692:
654:
620:
339:
335:
82:
1496:
1464:
1308:
1233:
1185:
1113:
1109:
851:
845:
789:
783:
754:
740:
682:
449:
1444:
1440:
1400:
1276:
1161:
1089:
1065:
879:
818:
746:
719:
674:
646:
612:
445:
386:
350:, and a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at the
327:
209:
891:
830:
768:
733:
1468:
1452:
1412:
1404:
1197:
1169:
1105:
1073:
1053:
1045:
937:
918:
887:
826:
764:
729:
664:
429:
425:
394:
279:
97:
983:
30:
1420:
1368:
1249:
1085:
1037:
987:
634:
630:
461:
421:
413:
342:
in 1984. He moved to the IIT Delhi as a full professor in 1990, and moved again to the
331:
271:
107:
1534:
1456:
1328:
1209:
1153:
1145:
1121:
1097:
776:
724:
541:
437:
232:
62:
658:
624:
1300:
1217:
1177:
1137:
1129:
899:
838:
375:
696:
992:
323:
227:
214:
1288:
1225:
1081:
750:
367:
151:
121:
883:
524:
299:
822:
678:
1372:
616:
637:; Vazirani, Vijay V. (1987), "Matching is as easy as matrix inversion",
650:
441:
745:, CPHC/BCS Distinguished Dissertations, Springer-Verlag, p. 120,
977:
193:
448:
matching problem, and found a solution to this problem with optimal
250:
366:
Vazirani's research career has been centered around the design of
311:
51:
511:
385:
During the 1980s, he made seminal contributions to the classical
996:
742:
Randomized algorithms: approximation, generation, and counting
307:
302:
but in his second year he transferred to MIT and received his
72:
605:
algorithm for finding maximum matching in general graphs",
1576:
2005 fellows of the
Association for Computing Machinery
346:
in 1995. He was also a McKay
Visiting Professor at the
284:
Donald Bren School of
Information and Computer Sciences
598:{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}
551:
412:
His research results also include proving, along with
608:
Proc. 21st IEEE Symp. Foundations of
Computer Science
550:
298:
Vazirani first majored in electrical engineering at
1269:
1030:
282:distinguished professor of computer science in the
245:
220:
208:
192:
166:
147:
114:
103:
89:
68:
58:
44:
21:
785:Computational Complexity: A Conceptual Perspective
597:
844:Williamson, David P.; Shmoys, David B. (2011),
464:(also a theoretical computer scientist, at the
1008:
16:Indian American professor of computer science
8:
1551:Massachusetts Institute of Technology alumni
850:, Cambridge University Press, p. 191,
788:, Cambridge University Press, p. 229,
1015:
1001:
993:
18:
1556:University of California, Berkeley alumni
951:"2022 INFORMS Annual Meeting Awards Hall"
723:
586:
578:
568:
560:
558:
549:
1571:University of California, Irvine faculty
670:Proc 22nd ACM Symp. Theory of Computing
504:
389:problem, and some key contributions to
847:The Design of Approximation Algorithms
460:In 2005 both Vazirani and his brother
1596:Indian emigrants to the United States
436:), and obtaining in 1980, along with
300:Indian Institute of Technology, Delhi
179:Indian Institute of Technology, Delhi
7:
1616:American academics of Indian descent
1591:20th-century American mathematicians
470:Association for Computing Machinery
326:. After postdoctoral research with
199:Maximum Matchings without Blossoms
1586:20th-century Indian mathematicians
468:) were inducted as Fellows of the
466:University of California, Berkeley
352:California Institute of Technology
348:University of California, Berkeley
320:Maximum Matchings without Blossoms
316:University of California, Berkeley
78:University of California, Berkeley
14:
1606:American people of Sindhi descent
931:ACM Fellows Award: Vijay Vazirani
912:ACM Fellows Award: Umesh Vazirani
356:University of California, Irvine
288:University of California, Irvine
184:University of California, Irvine
29:
1581:Theoretical computer scientists
479:In 2022, Vazirani received the
391:computational complexity theory
372:computational complexity theory
344:Georgia Institute of Technology
174:Georgia Institute of Technology
156:computational complexity theory
591:
587:
579:
569:
561:
555:
544:; Vazirani, V. V. (1980), "An
1:
1024:John von Neumann Theory Prize
529:Mathematics Genealogy Project
494:List of Indian mathematicians
481:John von Neumann Theory Prize
132:John von Neumann Theory Prize
725:10.1016/0304-3975(86)90174-X
712:Theoretical Computer Science
472:. In 2011, he was awarded a
358:as distinguished professor.
955:2022 INFORMS Annual Meeting
513:Deutsche Nationalbibliothek
338:, he joined the faculty at
318:in 1983. His dissertation,
1632:
1561:Cornell University faculty
936:December 14, 2007, at the
917:December 14, 2007, at the
354:. In 2017 he moved to the
751:10.1007/978-1-4471-0695-1
306:in computer science from
275:
241:
140:
28:
986:publications indexed by
782:Goldreich, Oded (2008),
434:ValiantâVazirani theorem
407:approximation algorithms
403:approximation algorithms
399:Valiant-Vazirani theorem
370:, together with work on
94:ValiantâVazirani theorem
884:10.1145/1284320.1284321
380:algorithmic game theory
268:Vijay Virkumar Vazirani
160:algorithmic game theory
1513:Christos Papadimitriou
1353:Arthur F. Veinott, Jr.
1258:R. Tyrrell Rockafellar
599:
276:à€”à€żà€à€Ż à€”à„à€°à€à„à€źà€Ÿà€° à€”à€à€Œà„à€°à€Ÿà€šà„
1433:Jean Bernard Lasserre
823:10.1145/375827.375845
739:Bubley, Russ (2001),
679:10.1145/100216.100262
600:
474:Guggenheim Fellowship
127:Guggenheim Fellowship
1611:Indian Sindhi people
1566:Georgia Tech faculty
673:, pp. 352â358,
617:10.1109/SFCS.1980.12
548:
322:, was supervised by
294:Education and career
1345:Alexander Schrijver
1321:J. Michael Harrison
75:(Bachelor's degree)
1517:Mihalis Yannakakis
1477:Dimitris Bertsimas
1297:Donald L. Iglehart
1281:Manfred W. Padberg
878:(5): Art. 22, 19,
872:Journal of the ACM
811:Journal of the ACM
651:10.1007/BF02579206
635:Vazirani, Umesh V.
611:, pp. 17â27,
595:
594:
340:Cornell University
336:Harvard University
83:Harvard University
1528:
1527:
1521:
1509:
1501:
1497:Alexander Shapiro
1493:
1485:
1473:
1465:Dimitri Bertsekas
1461:
1449:
1437:
1425:
1417:
1409:
1397:
1393:Gérard Cornuéjols
1389:
1377:
1365:
1357:
1349:
1333:
1325:
1317:
1309:Arkadi Nemirovski
1305:
1293:
1285:
1262:
1254:
1246:
1238:
1234:Peter C. Fishburn
1230:
1222:
1214:
1206:
1194:
1186:Richard E. Barlow
1182:
1174:
1166:
1158:
1150:
1142:
1134:
1126:
1118:
1114:Richard J. Duffin
1110:William W. Cooper
1102:
1094:
1078:
1070:
1058:
1050:
1042:
573:
456:Awards and honors
450:competitive ratio
304:bachelor's degree
278:; b. 1957) is an
265:
264:
221:Doctoral students
142:Scientific career
1623:
1519:
1507:
1499:
1491:
1483:
1471:
1459:
1447:
1445:Ruth J. Williams
1441:Martin I. Reiman
1435:
1423:
1415:
1407:
1401:George Nemhauser
1395:
1387:
1375:
1363:
1355:
1347:
1337:Martin Grötschel
1331:
1323:
1315:
1303:
1291:
1283:
1277:Ellis L. Johnson
1260:
1252:
1244:
1236:
1228:
1220:
1212:
1204:
1192:
1180:
1172:
1164:
1162:Herbert A. Simon
1156:
1148:
1140:
1132:
1124:
1116:
1100:
1092:
1090:Albert W. Tucker
1076:
1068:
1066:Carlton E. Lemke
1056:
1048:
1040:
1017:
1010:
1003:
994:
966:
965:
963:
962:
957:. 5 October 2022
947:
941:
928:
922:
909:
903:
902:
867:
861:
860:
841:
806:
800:
798:
779:
736:
727:
718:(2â3): 169â188,
707:
701:
699:
665:Karp, Richard M.
661:
627:
604:
602:
601:
596:
590:
582:
574:
572:
564:
559:
537:
531:
522:
516:
509:
387:maximum matching
328:Michael O. Rabin
310:in 1979 and his
277:
261:
258:
256:
254:
252:
210:Doctoral advisor
204:
33:
19:
1631:
1630:
1626:
1625:
1624:
1622:
1621:
1620:
1601:American Hindus
1531:
1530:
1529:
1524:
1469:John Tsitsiklis
1453:Donald Goldfarb
1413:Michel Balinski
1405:Laurence Wolsey
1313:Michael J. Todd
1265:
1198:Alan J. Hoffman
1170:Harry Markowitz
1106:Abraham Charnes
1074:David Blackwell
1054:Felix Pollaczek
1046:Richard Bellman
1026:
1021:
974:
969:
960:
958:
949:
948:
944:
938:Wayback Machine
929:
925:
919:Wayback Machine
910:
906:
869:
868:
864:
858:
843:
808:
807:
803:
796:
781:
761:
738:
709:
708:
704:
689:
663:
631:Mulmuley, Ketan
629:
546:
545:
540:
538:
534:
523:
519:
510:
506:
502:
490:
458:
395:isolation lemma
364:
296:
280:Indian American
249:
237:
202:
188:
136:
98:Isolation lemma
81:
76:
69:Alma mater
54:
49:
40:
24:
17:
12:
11:
5:
1629:
1627:
1619:
1618:
1613:
1608:
1603:
1598:
1593:
1588:
1583:
1578:
1573:
1568:
1563:
1558:
1553:
1548:
1543:
1533:
1532:
1526:
1525:
1523:
1522:
1510:
1505:Vijay Vazirani
1502:
1494:
1486:
1474:
1462:
1450:
1438:
1426:
1421:Nimrod Megiddo
1418:
1410:
1398:
1390:
1385:Peter W. Glynn
1381:SĂžren Asmussen
1378:
1369:Yurii Nesterov
1366:
1358:
1350:
1334:
1326:
1318:
1306:
1294:
1286:
1273:
1271:
1267:
1266:
1264:
1263:
1255:
1250:Fred W. Glover
1247:
1239:
1231:
1223:
1215:
1207:
1195:
1190:Frank Proschan
1183:
1175:
1167:
1159:
1151:
1143:
1135:
1127:
1119:
1103:
1095:
1086:Harold W. Kuhn
1079:
1071:
1059:
1051:
1043:
1038:George Dantzig
1034:
1032:
1028:
1027:
1022:
1020:
1019:
1012:
1005:
997:
991:
990:
988:Google Scholar
984:Vijay Vazirani
981:
973:
972:External links
970:
968:
967:
942:
923:
904:
862:
856:
817:(2): 274â296,
801:
794:
759:
702:
687:
645:(1): 105â113,
593:
589:
585:
581:
577:
571:
567:
563:
557:
554:
532:
525:Vijay Vazirani
517:
503:
501:
498:
497:
496:
489:
486:
462:Umesh Vazirani
457:
454:
414:Leslie Valiant
363:
360:
332:Leslie Valiant
295:
292:
263:
262:
247:
243:
242:
239:
238:
236:
235:
230:
224:
222:
218:
217:
212:
206:
205:
196:
190:
189:
187:
186:
181:
176:
170:
168:
164:
163:
149:
145:
144:
138:
137:
135:
134:
129:
124:
118:
116:
112:
111:
108:Umesh Vazirani
105:
101:
100:
91:
90:Known for
87:
86:
70:
66:
65:
60:
56:
55:
50:
46:
42:
41:
34:
26:
25:
23:Vijay Vazirani
22:
15:
13:
10:
9:
6:
4:
3:
2:
1628:
1617:
1614:
1612:
1609:
1607:
1604:
1602:
1599:
1597:
1594:
1592:
1589:
1587:
1584:
1582:
1579:
1577:
1574:
1572:
1569:
1567:
1564:
1562:
1559:
1557:
1554:
1552:
1549:
1547:
1546:Living people
1544:
1542:
1539:
1538:
1536:
1518:
1514:
1511:
1506:
1503:
1498:
1495:
1490:
1487:
1482:
1481:Jong-Shi Pang
1478:
1475:
1470:
1466:
1463:
1458:
1457:Jorge Nocedal
1454:
1451:
1446:
1442:
1439:
1434:
1430:
1429:VaĆĄek ChvĂĄtal
1427:
1422:
1419:
1414:
1411:
1406:
1402:
1399:
1394:
1391:
1386:
1382:
1379:
1374:
1370:
1367:
1362:
1359:
1354:
1351:
1346:
1342:
1341:LĂĄszlĂł LovĂĄsz
1338:
1335:
1330:
1329:Robert Aumann
1327:
1322:
1319:
1314:
1310:
1307:
1302:
1298:
1295:
1290:
1287:
1282:
1278:
1275:
1274:
1272:
1268:
1259:
1256:
1251:
1248:
1243:
1242:Peter Whittle
1240:
1235:
1232:
1227:
1224:
1219:
1216:
1211:
1210:Robert Herman
1208:
1203:
1199:
1196:
1191:
1187:
1184:
1179:
1176:
1171:
1168:
1163:
1160:
1155:
1154:Samuel Karlin
1152:
1147:
1146:Kenneth Arrow
1144:
1139:
1136:
1131:
1128:
1123:
1122:Herbert Scarf
1120:
1115:
1111:
1107:
1104:
1099:
1098:Lloyd Shapley
1096:
1091:
1087:
1083:
1080:
1075:
1072:
1067:
1063:
1060:
1055:
1052:
1047:
1044:
1039:
1036:
1035:
1033:
1029:
1025:
1018:
1013:
1011:
1006:
1004:
999:
998:
995:
989:
985:
982:
979:
976:
975:
971:
956:
952:
946:
943:
939:
935:
932:
927:
924:
920:
916:
913:
908:
905:
901:
897:
893:
889:
885:
881:
877:
873:
866:
863:
859:
857:9781139498173
853:
849:
848:
840:
836:
832:
828:
824:
820:
816:
812:
805:
802:
797:
795:9781139472746
791:
787:
786:
778:
774:
770:
766:
762:
760:1-85233-325-1
756:
752:
748:
744:
743:
735:
731:
726:
721:
717:
713:
706:
703:
698:
694:
690:
688:0-89791-361-2
684:
680:
676:
672:
671:
666:
660:
656:
652:
648:
644:
640:
639:Combinatorica
636:
632:
626:
622:
618:
614:
610:
609:
583:
575:
565:
552:
543:
536:
533:
530:
526:
521:
518:
515:
514:
508:
505:
499:
495:
492:
491:
487:
485:
482:
477:
475:
471:
467:
463:
455:
453:
451:
447:
443:
439:
438:Silvio Micali
435:
431:
427:
423:
419:
415:
410:
408:
404:
400:
396:
392:
388:
383:
381:
377:
373:
369:
361:
359:
357:
353:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
309:
305:
301:
293:
291:
289:
285:
281:
273:
269:
260:
248:
244:
240:
234:
233:Samir Khuller
231:
229:
226:
225:
223:
219:
216:
213:
211:
207:
200:
197:
195:
191:
185:
182:
180:
177:
175:
172:
171:
169:
165:
161:
157:
153:
150:
146:
143:
139:
133:
130:
128:
125:
123:
120:
119:
117:
113:
109:
106:
102:
99:
95:
92:
88:
84:
79:
74:
71:
67:
64:
61:
57:
53:
47:
43:
38:
32:
27:
20:
1504:
1489:Adrian Lewis
1301:Cyrus Derman
1270:2000âpresent
1218:Lajos Takacs
1202:Philip Wolfe
1178:Richard Karp
1138:Jack Edmonds
1130:Ralph Gomory
1062:John F. Nash
980:at UC Irvine
959:. Retrieved
954:
945:
926:
907:
875:
871:
865:
846:
814:
810:
804:
784:
741:
715:
711:
705:
668:
642:
638:
606:
535:
520:
512:
507:
478:
459:
411:
393:, e.g., the
384:
376:cryptography
365:
319:
297:
267:
266:
198:
167:Institutions
141:
1541:1951 births
1361:Frank Kelly
324:Manuel Blum
228:Naveen Garg
215:Manuel Blum
59:Nationality
1535:Categories
1289:Ward Whitt
1226:Egon Balas
1082:David Gale
961:2022-11-08
542:Micali, S.
500:References
418:UNIQUE-SAT
416:, that if
368:algorithms
259:/~vazirani
152:algorithms
122:ACM Fellow
1031:1975â1999
978:Home page
777:266744010
576:⋅
314:from the
110:(brother)
104:Relatives
85:(PostDoc)
37:UC Irvine
1373:Yinyu Ye
934:Archived
915:Archived
659:47370049
625:27467816
488:See also
362:Research
63:American
900:8481313
892:2359264
839:2353092
831:1868717
769:1986183
734:0855970
527:at the
442:AdWords
424:, then
286:at the
246:Website
1520:(2023)
1508:(2022)
1500:(2021)
1492:(2020)
1484:(2019)
1472:(2018)
1460:(2017)
1448:(2016)
1436:(2015)
1424:(2014)
1416:(2013)
1408:(2012)
1396:(2011)
1388:(2010)
1376:(2009)
1364:(2008)
1356:(2007)
1348:(2006)
1332:(2005)
1324:(2004)
1316:(2003)
1304:(2002)
1292:(2001)
1284:(2000)
1261:(1999)
1253:(1998)
1245:(1997)
1237:(1996)
1229:(1995)
1221:(1994)
1213:(1993)
1205:(1992)
1193:(1991)
1181:(1990)
1173:(1989)
1165:(1988)
1157:(1987)
1149:(1986)
1141:(1985)
1133:(1984)
1125:(1983)
1117:(1982)
1101:(1981)
1093:(1980)
1077:(1979)
1069:(1978)
1057:(1977)
1049:(1976)
1041:(1975)
898:
890:
854:
842:. See
837:
829:
792:
775:
767:
757:
737:. See
732:
697:822904
695:
685:
657:
623:
446:online
444:as an
420:is in
397:, the
378:, and
203:(1985)
201:
194:Thesis
148:Fields
115:Awards
39:, 2021
896:S2CID
835:S2CID
773:S2CID
693:S2CID
655:S2CID
621:S2CID
312:Ph.D.
272:Hindi
80:(PhD)
52:India
852:ISBN
790:ISBN
755:ISBN
683:ISBN
330:and
257:.edu
255:.uci
253:.ics
48:1957
45:Born
880:doi
819:doi
747:doi
720:doi
675:doi
647:doi
613:doi
334:at
308:MIT
251:www
73:MIT
35:At
1537::
1515:/
1479:/
1467:/
1455:/
1443:/
1431:/
1403:/
1383:/
1371:/
1343:/
1339:/
1311:/
1299:/
1279:/
1200:/
1188:/
1112:/
1108:/
1088:/
1084:/
1064:/
953:.
894:,
888:MR
886:,
876:54
874:,
833:,
827:MR
825:,
815:48
813:,
780:;
771:,
765:MR
763:,
753:,
730:MR
728:,
716:43
714:,
691:,
681:,
662:;
653:,
641:,
633:;
628:;
619:,
476:.
452:.
430:RP
428:=
426:NP
382:.
374:,
290:.
274::
158:,
154:,
96:,
1016:e
1009:t
1002:v
964:.
940:.
921:.
882::
821::
799:.
749::
722::
700:.
677::
649::
643:7
615::
592:)
588:|
584:E
580:|
570:|
566:V
562:|
556:(
553:O
432:(
422:P
270:(
162:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
