GI-Preis

Lederer, Patrick

Preisträger Patrick Lederer mit Laudator Wolfgang Glock (Foto: Thorsten Jochim)

Der Bachelor-Absolvent Patrick Lederer wurde im Rahmen des Absolventenfestes aufgrund seiner herausragenden Bachelor-Arbeit mit dem Titel "Analysis of a Randomized Sparsest Cut Heuristic" (Lehrstuhl für Theoretische Informatik, Prof. Harald Räcke) mit dem GI-Preis der Gesellschaft für Informatik e. V. geehrt. In diesem Jahr wurde die Auszeichnung von der mgm technolgoy partners GmbH gesponsort. Überbringer des Preises war Wolfgang Glock von der Landeshauptstadt München, Sprecher der Regionalgruppe München und Mitglied im erweiterten Vorstand der GI.

In dieser Bachelorarbeit ging es darum, eine einfache Heuristik für das sogenannte „Sparsest Cut Problem“ theoretisch zu analysieren. Es gibt für dieses Problem eine sehr einfache (randomisierte) Heuristik die eine sehr gute Laufzeit besitzt und von der vermutet wird, dass der gefundene Engpass immer nahezu optimal ist. Patrick Lederer hat diese Vermutung in seiner Arbeit für einige einfache Graphen wie z. B. reguläre Bäume, Kreise, Sterne etc. formal bewiesen. Hierbei hat er mit außerordentlicher Kreativität verschiedene Methoden entwickelt, um den randomisierten Prozess, der sich durch die Heuristik ergibt, zu analysieren. Darüberhinaus hat der Bachelor-Absolvent sehr exakt die Limitierungen der einzelnen Ansätze herausgearbeitet und eine Reihe von Vermutungen aufgestellt, deren Beweis Resultate für größere Graphklassen ergeben würden. Damit hat Patrick Lederer einen wesentlichen Fortschritt auf diesem Gebiet erzielt, auf dem weitere Arbeiten aufbauen können.