Dr. Markus Bläser

"Algorithmische Probleme in Netzwerken"

Probleme in Netzwerken sind seit jeher zentrale Probleme der Algorithmik. Klassisch stehen meist Optimierungsprobleme im Vordergrund, die oftmals schwer – sprich NP-hart – sind. Approximationsalgorithmen sind ein Ansatz, um NP-harte Probleme (näherungsweise) zu lösen. Im ersten Teil des Vortrags steht dieses Konzept der Approximationsalgorithmen im Vordergrund, das wir am Beispiel des Traveling Salesperson Problems, einem klassischen Netzwerk-Problems, veranschaulichen.

Neuerdings werden Netzwerkprobleme in der Informatik nicht nur unter Optimierungsaspekten betrachtet, sondern auch unter spieltheoretischen Gesichtspunkten. Dies ist motiviert durch die Modellierung möglicher künftiger Internet-Szenarien. Diese neuen Entwicklungen werden wir im zweiten Teil des Vortrags exemplarisch darstellen. Hauptaugenmerk liegt dabei auf dem sogenannten Multicast Cost-Sharing Problem.