Mihalis Yannakakis (griechisch Μιχάλης Γιαννακάκης Michalis Giannakakis; * 13. September 1953 in Athen) ist ein griechischer Informatiker.

Yannakakis erwarb 1975 sein Diplom in Elektrotechnik an der Nationalen Technischen Universität in Athen. 1979 wurde er an der Princeton University bei Jeffrey Ullman promoviert. Seit 1978 war er an den Bell Laboratories, wo er ab 1991 das Computing Principles Research Department leitete. Ab 2001 war er in gleicher Funktion an den Avaya Laboratories in Basking Ridge (New Jersey). 2002 wurde er Professor für Informatik an der Stanford University und ab 2004 an der Columbia University.

Er befasst sich mit Algorithmendesign und -analyse, kombinatorischer Optimierung, Datenbanken (speziell begründete er das Studium azyklischer Datenbanken), computergestützte Testverfahren und Verifikationsverfahren, algorithmische Graphentheorie und Komplexitätstheorie. 1988 führte er mit Christos Papadimitriou neue Komplexitätsklassen ein (Max-NP und dessen Unterklasse Max-SNP), zu denen auch bekannte Probleme wie das Problem des Handlungsreisenden und 3-SAT gehören. Einflussreich war auch seine Arbeit mit Carsten Lund über die Schwierigkeit, Näherungsverfahren für NP-schwierige Minimierungsprobleme wie dem Graphenfärbungsproblem und dem Mengenüberdeckungsproblem zu erhalten. 1991 veröffentlichte er eine Arbeit, die die Erweiterungskomplexität (Extension complexity) von Polytopen in der kombinatorischen Optimierung mit anderen Komplexitätskonzepten verband.

1997 wurde er Fellow der Bell Laboratories, 1985 erhielt er den Distinguished Member of Technical Staff Award des Labors und 2000 erhielt er die Goldmedaille des Präsidenten der Bell Labs. 2005 erhielt er den Knuth-Preis, für 2020 wurde ihm der EATCS-Award zugesprochen. Seit 1998 ist er Fellow der Association for Computing Machinery (ACM). 2013 wurde er als auswärtiges Mitglied in die Academia Europaea aufgenommen, 2018 in die National Academy of Sciences. 1992 bis 2003 war er Mit-Herausgeber und ab 1998 Haupt-Herausgeber des SIAM Journal of Computing. Außerdem war er 1986 bis 2000 Mitherausgeber des Journal of the ACM und ist seit 1997 Mitherausgeber des Journal of Combinatorial Optimization und seit 2004 des Journal of Complexity.

2020 wurde Yannakakis in die American Academy of Arts and Sciences gewählt.

Einzelnachweise

  1. ↑ Papadimitriou, Yannakakis: Optimization, approximation, and complexity classes, Proceedings of the 20th annual ACM symposium on Theory of computing, Mai 1988, S. 229–234
  2. ↑ Lund, Yannakakis: On the hardness of approximating minimization problems, Proceedings of the 25th annual ACM symposium on Theory of computing, Mai 1993, S. 286–293
  3. ↑ Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci., Band 43, 1991, S. 441–466
  4. ↑ Mitgliederverzeichnis: Mihalis Yannakakis. Academia Europaea, abgerufen am 22. Januar 2018 (englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.