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 Arbeit von Vladimir Kolmogorovs Gruppe lässt sich in drei Themengebiete unterteilen. Das erste Gebiet ist die Entwicklung effizienter Algorithmen für die Inferenz in graphischen Modellen und kombinatorischen Optimierungsproblemen. Manche der Techniken werden häufig für „Computer Vision“ und andere Gebiet eingesetzt, wie entweder der „Boykov-Kolmogorov“ Maximum Flow Algorithmus und der „TRW-S“ Algorithmus für MAP Inferenz in paarweisen graphischen Modellen. Kolmogorovs „Blossom V“ Algorithmus ist die derzeit schnellste Technik für die Berechnung des „minimum cost perfect matching“ in einem Graphen. Der zweite Schwerpunkt der Gruppe liegt auf theoretischen Studien zur Komplexität diskreter Optimierung, insbesondere im Rahmen der „valued constraint satisfaction“ Probleme und ihrer Varianten. Zusätzlich arbeitet die Kolmogorov-Gruppe an Anwendungen der diskreten Optimierung für „Computer Vision“, wie etwa in der Bildunterteilung und der Stereorekonstruktion.