Res­sourcen im In­ter­net ef­f­iz­ient nutzen – Ju­ni­or­pro­fess­or Dr. Patrick Bri­est en­twirft Al­gorith­men zur Pre­iso­p­ti­mier­ung

Hier die etwas verspätete <link fileadmin uni-aktuell pressefotos dezember forschung_insight_07_november_2010.pdf _blank>November-Ausgabe der "Forschung inSight" des Instituts für Informatik: Seit September 2009 arbeitet Patrick Briest als Juniorprofessor am Institut für Informatik der Universität Paderborn. Der gebürtige Bottroper gehört der Fachgruppe „Algorithmen und Komplexität“ an und kümmert sich insbesondere um das Zusammenspiel autonomer Softwaresysteme.

Ein Schwerpunkt der Arbeit des Juniorprofessors, der vor seiner Berufung an die Universität Paderborn bereits in Dortmund, Liverpool und New York Station gemacht hat, liegt auf der Anwendung von Algorithmen und spieltheoretischen Prinzipien in großen verteilten Systemen wie beispielsweise dem Internet. Auf der Plattform Internet agieren viele verschiedene autonome Systeme miteinander, von denen jedes Einzelne zunächst seine eigenen Interessen verfolgt. Um ein funktionsfähiges Gesamtsystem zur erhalten, müssen die Protokolle, die das Zusammenspiel der einzelnen Akteure regeln, Anreize zur Kooperation liefern. Gleichzeitig müssen aufgrund der immensen Größe des Systems die verwendeten algorithmischen Verfahren möglichst effizient sein, um mit der vorhandenen Rechenleistung und Speicherkapazität auszukommen.

„Die Spieltheorie ist in den Wirtschaftswissenschaften entstanden und wir untersuchen nun, wie sich spieltheoretische und effiziente algorithmische Lösungen kombinieren und auf grundlegende Probleme anwenden lassen“, erklärt Patrick Briest. Gemeinsam mit weiteren Mitarbeitern des Instituts für Informatik und Kollegen in den USA sucht er daher zum Beispiel nach effizienten Algorithmen für die kombinatorische Preisoptimierung. Diese spielt etwa bei der Platzierung von Werbung in Suchmaschinen eine wichtige Rolle.

„Es geht im Grunde um das altbekannte Problem, erlösmaximierende Preise für eine gegebene Menge von Produkten zu finden – das gab es durchaus schon vor dem Internet“, berichtet der Juniorprofessor. Damit dies möglich ist, müssen zunächst Informationen über die Präferenzen potentieller Kunden gesammelt und ausgewertet werden. Auf Basis dieser umfangreichen Daten können dann algorithmische Optimierungsverfahren entworfen werden. Um Effizienz garantieren zu können, kommen hier in der Regel approximative bzw. randomisierte, das heißt zufallsgesteuerte, Verfahren zum Einsatz.

„Mit Hilfe dieser Verfahren können zum Beispiel auch Online-Händler herausfinden, wie viel mehr Geld sie möglicherweise noch für ein bestimmtes Produkt bekommen könnten“, erzählt Patrick Briest. „Denn es ist ja tatsächlich so, dass die Preisauszeichnung im Internet viel variabler ist als in der Offline-Welt, da man sie nicht überprüfen kann“, fügt er an.

In diesem Zusammenhang interessiert sich der Informatiker auch für im Internet mittlerweile weit verbreitete alternative Vertriebskonzepte. Denn immer wieder werden Methoden zur Preisdiskriminierung, wie zum Beispiel die Bündelung von Produkten, mit dem Ziel der Erlössteigerung eingesetzt. Beispiele reichen von Hotelbuchungen auf Plattformen wie hotwire.com bis zu Handyverträgen mit „Kostenairbag“.

Generell ist der Algorithmenentwurf einer der zentralen und ältesten Zweige der Informatik. Die Forschung am Paderborner Institut für Informatik konzentriert sich hierbei auf Fragestellungen, in denen aktuelle technische Möglichkeiten wie beispielsweise mobile Kommunikationsnetze oder Hochleistungsrechnernetzwerke neue Herausforderung für den Entwurf effizienter Algorithmen darstellen.
 

Autor: Katharina Bätz

Foto: Die Plattform Internet bietet Juniorprofessor Patrick Briest viel Raum für Forschung.
Foto: Die Plattform Internet bietet Juniorprofessor Patrick Briest viel Raum für Forschung.