Randomisierte Algorithmen

Im letzten Jahrzehnt haben randomisierte Algorithmen enorm an Bedeutung gewonnen. Während dieser Periode sind sie von einem Werkzeug aus der Zahlentheorie zu einem der bedeutensten algorithmischen Konzepte mit weitreichenden Anwendungen in verschiedenen Gebieten geworden. Randomisierte Algorithmen sind dabei Algorithmen, die sich im Gegensatz zu deterministischen Algorithmen den Zufall zunutze machen. Zwei Vorteile gehen in der Regel mit randomisierten Algorithmen einher, Einfachheit und Geschwindigkeit. Für viele Anwendungen sind die randomisierten Algorithmen entweder die einfachsten, die schnellsten oder vereinen beide Vorteile. Unsere Forschung, in Kooperation mit Ravi Kannan (Department of Computer Science, Yale University) und Leen Stougie (Department of Computer Science, Eindhoven University) konzentrierte sich auf drei Anwendungen von randomisierten Algorithmen: