Max-Planck-Institut für Informatik Saarbrücken
emeritierter Direktor
Wer bekommt was? Faire Zuteilung von unteilbaren Gütern.
Eine Menge von unteilbaren Gütern, etwa ein Haus, ein Computer, eine Zahnbürste, … soll auf eine Gruppe von Personen aufgeteilt werden. Jede Person hat ihre eigene Vorstellung über den Wert der Güter. In einer solchen Situation kann man Neid nicht vermeiden. Wenn es etwa nur ein Gut gibt, das aber zwischen zwei Personen aufgeteilt werden soll, muss man das Gut einer der beiden Personen geben. Die andere wird neidisch sein. Wie weit kann man Neid vermeiden? Kann man etwa folgendes bei zwei Personen erreichen: Jede Person bekommt eine Teilmenge der Güter und kann danach eine der folgenden Aussagen treffen: Mein Bündel ist mir lieber als Deines. Oder: Dein Bündel ist mir zwar lieber als meines aber nach Entfernung eines beliebigen Guts aus Deinem Bündel ziehe ich meines vor. Bei zwei Personen geht das immer. Geht es auch bei drei oder vieren oder …?
Zur Person
Kurt Mehlhorn studierte von 1968 bis 1971 Mathematik und Informatik an der Technischen Universität München und promovierte 1974 an der Cornell University in Ithaca (New York) bei Robert Lee Constable mit dem Thema „Polynomial and Abstract Sub-recursive Classes“. Er ging anschließend an die Universität des Saarlandes in Saarbrücken und wurde 1975 zum Professor ernannt. Von 1990 bis 2019 war er Direktor am Max-Planck-Institut für Informatik in Saarbrücken und seit August 2016 im wissenschaftlichen Rat des Europäischen Forschungsrates. Von 2002 bis 2008 war er Vizepräsident der Max-Planck-Gesellschaft. Schwerpunkt seiner Arbeit sind effiziente Algorithmen für kombinatorische und geometrische Probleme, kombinatorische Optimierung, „Algorithm-Engineering“ und Softwarebibliotheken. Er lieferte Arbeiten zur Optimierung und zur Komplexitätstheorie, zu Datenstrukturen und zu Algorithmen für Graphen und Geometrie. Von ihm verfasste Lehrbücher über Algorithmen und Datenstrukturen gehören zum grundlegenden Lehrkanon heutiger Informatikstudierende.