Kolmogorov Group

Diskrete Optimierung

Wenn wir auf die Straße gehen, beurteilen wir automatisch den Abstand und die Geschwindigkeit der herannahenden Autos. Computer müssen komplexe Berechnungen durchführen, um die Tiefe von Objekten in einem Bild zu schätzen. Ein beliebter Ansatz zur Lösung dieses Problems ist die Verwendung diskreter Optimierungsalgorithmen – dem Forschungsschwerpunkt der Kolmogorov Gruppe.

Die Gruppe um Vladimir Kolmogorov befasst sich in erster Linie mit diskreter und kombinatorischer Optimierung. Sie hat mehrere in der Fachwelt bekannte effiziente Algorithmen entwickelt, darunter den „Boykov-Kolmogorov”-Algorithmus für maximalen Fluss, den „Blossom V”-Algorithmus zur Berechnung einer minimalen perfekten Zuordnung in einem Graphen und den „TRW-S”-Algorithmus für MAP-MRF-Inferenz in grafischen Modellen. Die Gruppe hat sich mit Komplexitätsklassifikationen von Valued Constraint Satisfaction Problems (VCSPs) und deren Varianten befasst und zur Lösung eines wichtigen offenen Problems in diesem Bereich beigetragen. Neuere Arbeiten befassten sich mit dem Sparsest-Cut-Problem, dem Packen von Bäumen (einem Begriff der Grafentheorie) in Graphen, praktischen Algorithmen zur Berechnung des Gomory-Hu-Baums sowie einigen Themen außerhalb der diskreten Optimierung. Dazu gehören das Lovász-Local-Lemma, die Schätzung von Parametern von Gibbs-Verteilungen und die Zertifizierung von Lösungen von SDPs. In der Vergangenheit arbeitete die Kolmogorov Gruppe an Anwendungen der diskreten Optimierung in der Bildverarbeitung, wie beispielsweise der Stereo-Rekonstruktion und der Bildsegmentierung.