Das Partitioned Boolean Quadratic Problem (PBQP) ist ein NP-vollständiges mathematisches Optimierungsproblem.
Für das PBQP existieren lineare Heuristiken, die eine optimale Lösung für große Unterklassen des PBQP berechnen.
Sowohl die Heuristiken als auch optimale Lösungsansätze verfügen über großes Parallelisierungspotential.
Im Rahmen dieser Arbeit soll ein paralleler PBQP-Löser in der Programmiersprache X10 entwickelt werden.
Aufgabe
- Entwurf eines parallelen PBQP-Lösers
- Implementierung des PBQP-Lösers in X10
- Evaluierung der verwendeten Ansätze zur Parallelisierung
Literatur
Voraussetzungen
- Spaß an paralleler Programmierung mit X10
- Interesse an PBQP
Veröffentlichungen
Betreuer
Studenten