Vijay Vazirani

Vijay Virkumar Vazirani (* 20. April 1957) ist ein indischstämmiger US-amerikanischer Informatiker.

Vijay Vazirani, 2010, University of California, Berkeley.

Vazirani studierte am Massachusetts Institute of Technology (Bachelor-Abschluss 1979) und promovierte 1983 an der University of California, Berkeley bei Manuel Blum (Maximum matchings without blossoms). In den 1990er Jahren war er Professor am Indian Institute of Technology in Delhi. Er war Professor für Informatik am Georgia Institute of Technology. Er war unter anderem Gastprofessor in Berkeley. Seit 2017 ist er Professor an der University of California, Irvine.

Vazirani beschäftigte sich mit der Entwicklung von Approximations-Algorithmen (wie Jain-Vazirani Algorithmus in der Facility Location 2001), Paarungs-Algorithmen (Matching) in der Graphentheorie (mit Silvio Micali fand er 1980 einen verbesserten Algorithmus für maximale Paarungen in Graphen)[1], Komplexitätstheorie (wo er mit Leslie Valiant 1985 ein wichtiges Theorem bewies), Kryptographie, Codierungstheorie, algorithmischer Spieltheorie sowie Quanten-Informatik.

Sein Bruder Umesh Vazirani ist Informatik-Professor in Berkeley. Beide sind seit 2005 Fellows der Association for Computing Machinery (ACM).

Sein Vater V.N. Vazirani war Professor für Bauingenieurwesen.

Schriften

Approximation algorithms, Springer 2001
mit Noam Nisan, Éva Tardos, Tim Roughgarden (Herausgeber): Algorithmic Game Theory, Cambridge University Press 2007

Vazirani, Micali An $\textstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs, Proc. 21. IEEE Symposium Foundations Computer Science, 1980, S. 17–27 (|V|= Anzahl Ecken, |E|= Anzahl Kanten)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.