Vijay Vazirani

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Vijay Vazirani, 2010, University of California, Berkeley.

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

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 ist Professor für Informatik am Georgia Institute of Technology. Er war unter anderem Gastprofessor in Berkeley.

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[Bearbeiten]

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

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Vazirani, Micali An \scriptstyle 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)