Mihalis Yannakakis

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

Yannakakis an der Columbia University 2006

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.^[1]. Einflussreich war auch seine Arbeit mit Carsten Lund über die Schwierigkeit, Näherungsverfahren für NP-harte Minimierungsprobleme wie dem Graphenfärbungsproblem und dem Mengenüberdeckungsproblem zu erhalten.^[2]

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. Seit 1998 ist er Fellow der Association for Computing Machinery (ACM). 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.

Weblinks

• Homepage

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