Anwendungen des Maximum-Cut zur Lösung von Optimierungsproblemen

Proseminar

Der Bedarf an Rechenleistung steigt beständig. Das Lösen von Optimierungsproblemen ist heutzutage ein wichtiger Bestandteil. Während Prozessoren meist lange Rechenzeiten benötigen werden spezialisierte Ansätze entwickelt. Kommerziell erhältlich sind sogenannte digital Annealer, aber auch Ansätze mit anderen physikalischen Prinzipien werden erforscht. Als bekanntes Beispiel lassen sich Quantencomputer nennen.

Im Gegensatz zu klassischen Prozessoren werden Optimierungsprobleme direkt gelöst. Somit können beispielsweise Maximum-Cut Probleme sehr schnell und effizient bearbeitet werden. Jedoch müssen die in Anwendungen auftretenden Optimierungsprobleme zuerst auf Maximum-Cut Probleme abgebildet werden. Im Rahmen des Proseminars sollen praktische Anwendungen des Maximum-Cut, sowie damit verwandten Problemen recherchiert werden. Sofern möglich sollen essenzielle Kenngrößen wie ungefähre Anzahl an Knoten sowie deren Vernetzung gesammelt werden.

Aufgaben

• Ermittlung von Problemen, die sich mit dem Maximum-Cut abbilden lassen
• Recherche von praktischen Anwendungen für diese Probleme
• Untersuchung der gefunden Anwendungen bezüglich Anzahl der Knoten und deren Vernetzung