„Ravi Kannan“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
K r2.7.2) (Bot: Ergänze: hi:रविन्द्रन कन्नन, ht:Ravindran Kannan, ta:ரவி கண்ணன் |
|||
| Zeile 32: | Zeile 32: | ||
|STERBEORT= |
|STERBEORT= |
||
}} |
}} |
||
[[en:Ravi Kannan]] |
[[en:Ravi Kannan]] |
||
[[hi:रविन्द्रन कन्नन]] |
|||
[[ht:Ravindran Kannan]] |
|||
[[ta:ரவி கண்ணன்]] |
|||
Version vom 21. Mai 2012, 15:35 Uhr
Ravindran Kannan, genannt Ravi, (* 12. März 1953 in Madras)[1] ist ein indischer Informatiker und Mathematiker.
Leben
Kannan studierte am Indian Institute of Technology in Bombay und wurde 1980 an der Cornell University bei Leslie Earl Trotter promoviert (The size of numbers in the analysis of certain algorithms).[2] Er lehrte am Massachusetts Institute of Technology, war in den 1990er Jahren Professor an der Carnegie Mellon University und danach an der Yale University. Er ist zur Zeit Principal Research Scientist bei Microsoft Research in Indien (wo er die Forschungsgruppe für Algorithmen leitet) und lehrt am Indian Institute of Science in Bangalore.
Werk
Mit Alan M. Frieze fand er eine algorithmische Version des Regularitätslemmas von Endre Szemeredi.[3] In ihrer Arbeit führten sie das schwache Regularitätslemma ein, das ein wichtiges kombinatorisches Werkzeug für verschiedene Algorithmen wurde (Streaming Algorithms, Graph Limits, Sublinear Algorithms).
2011 erhielt er den Knuth-Preis für die Entwicklung einflussreicher algorithmischer Verfahren zur Lösung lange offener Berechnungsprobleme[4] mit Anwendungen auf die Verarbeitung umfangreicher Datenmengen, wobei er grundlegende Beiträge in sehr unterschiedlichen Bereichen der Informatik wie Gitter und ihre Anwendungen, geometrische Algorithmen, Maschinenlernen und numerische lineare Algebra leistete. Er befasste sich auch mit Markov-Ketten und deren Mischungszeiten, Clustering.[5]
1991 bekam er den Fulkerson-Preis für einen polynomzeitlichen Algorithmus zur Berechnung des Volumens beliebiger konvexer Körper.[6]
Ebenfalls 1991 löste er das Frobenius Problem und gab einen effizienten (polynomzeitlichen) Algorithmus zur Bestimmung der Frobenius Zahl.[7] Das nach Ferdinand Georg Frobenius benannte Problem (auch Münzproblem genannt) fragt nach der größten Zahl, die nicht aus n gegebenen Zahlen durch Addition erzeugt werden kann (diese Zahl ist die Frobeniuszahl). Wählt man z.B. im Fall von n=2 als Basis-Münzmenge 3 und 5, ist die Frobeniuszahl 7. Im Fall n=2 existiert sogar eine einfache Formel für die Frobeniuszahl, gefunden 1884 von James Joseph Sylvester (seien die Basiszahlen a,b, dann ist die Frobeniuszahl f=ab - a - b), ist n größer als 2 ist aber keine solche einfache Formel bekannt.
Mit Frieze und Santosh Vempala untersuchte er Näherungen niedrigen Rangs an Matrizen.[8]
Weblinks
Einzelnachweise
- ↑ Lebensdaten nach Marquis, Who´s Who in Frontiers in Science and Technology 1985
- ↑ Mathematics Genealogy Project
- ↑ Frieze, Kannan The regularity lemma and approximation schemes for dense problems, Proc. 37. Symposium Foundations of Computer Science (FOCS) 1996. Frieze, Kannan A simple algorithm for constructing Szemeredis regularity partition, Electronic J. Combinatorics, Band 6, 1999
- ↑ SIGACT, Würdigung für Knuth Preis 2011
- ↑ Frieze, Petros Drineas, Kannan, Vempala, V. Vinay Clustering in large graphs and matrices, Symposium on Discrete Algorithms (SODA) 1999
- ↑ Für: Martin E. Dyer, Alan M. Frieze and Ravindran Kannan A random polynomial time algorithm for approximating the volume of convex bodies, Journal of the ACM, Bd.38, 1991, S.1-17
- ↑ Kannan Lattice translates of a polytope and the Frobenius problem, Combinatorica, Band 12, 1992, S. 161-177
- ↑ Frieze, Kannan, Vempala Fast Monte Carlo algorithms for finding low rank approximants, Proc. FOCS 1998
| Personendaten | |
|---|---|
| NAME | Kannan, Ravi |
| ALTERNATIVNAMEN | Kannan, Ravindran |
| KURZBESCHREIBUNG | indischer Informatiker |
| GEBURTSDATUM | 12. März 1953 |
| GEBURTSORT | Madras |