Die Themenvorschläge finden Sie im OLAT. Zur Ansicht müssen Sie sich mit Ihrer stu-Kennung und Ihrem Passwort einloggen.

Der Themenordner sollte nach dem Einloggen direkt angezeigt werden. Wenn nicht, klicken Sie nochmals auf den obigen Link.

Alternativ finden Sie den Themenordner unter
Lernresourcen > Katalog > 11 Technische Fakultät > Informatik > Arbeitsgruppen > Theorie der Parallelität.

Betreuung Kim-Manuel Klein & Prof. Klaus Jansen

• Bin Packing
  • Abstand von Lösungswerten (Integrality Gap) berechnen
  • Integrality Gap untersuchen
  • Abstand (LP/ILP-Gap) von Lösungen
  • Anzahl Nicht-Null-Komponenten bei Lösungen
  • Schnellerer Approximationsalgorithmus (AFPTAS)
• Das Dial-A-Ride-Problem - Abholung und Beförderung in Taxiunternehmen
• Verallgemeinerung von Max-Min und Min-Max Resource Sharing - schnellere Verfahren für lineare Programme
• Scheduling von parallelen Jobs - Optimierung für einen besonderen Zielfunktionswert

Betreuung Maren Kaluza & Prof. Klaus Jansen

• Mehrdimensionales (d-dimensionales) Bin Packing - schnellere Algorithmen und untere Schranken zur Laufzeit
• Rucksackproblem (Knapsack) - Untere Schranken zur Laufzeit
• Strip Packing mit mehreren Streifen (Multiple Strip Packing) - schnellere und bessere Algorithmen
• Strip Packing mit beliebigen Rotationen

Betreuung Felix Land & Prof. Klaus Jansen

• Glasfaserverlegung
• Komplexität & Algorithmen für
  • Scheduling von malleable tasks (verformbarer Jobs)
  • Scheduling mit Präzedenzen
  • Strip Packing mit wenigen Itemtypen
• Stundenplanerstellung

Betreuung Marten Maack & Prof. Klaus Jansen

• Restricted Assignment - bessere Algorithmen bei
  
  • wenigen Ausführungszeiten oder
  • geordneten Einschränkungen
• Perodisches Scheduling of Public Transportation Services
• Produktionsplanung in der Holzwirtschaft
• Packing Squares into a Rectangle - bessere untere und obere Schranken
• 2D Strip Packing
  • Bessere Approximation für Strip Packing
  • 2D-Strip Packing mit wenigen Rechtecken - Exakte Algorithmen für das 2D-Platzierungsproblem (Zuschnittsproblem) & untere Schranken für die Laufzeit

Betreuung Kati Land & Prof. Klaus Jansen

• Restricted Assignment - Untersuchung des Abstands von Lösungen (Integrality Gap)
  

Betreuung Malin Rau & Prof. Klaus Jansen

• 2D Strip Packing - bessere Approximation
• Rucksackproblem (Knapsack) - Schnellerer Approximationsalgorithmus bei beschränkten Effizienzen
• 2D Bin Packing - bessere Rundung (und Approximation) bei dicken Rechtecken
• Resource Constrained Scheduling: Scheduling
  • mit einer zusätzlichen Ressource - bessere Approximation
  • mit mehreren Ressourcen - bessere Approximation

Betreuung Marcin Pal & Prof. Klaus Jansen

• Färbung von dichten Unit-Disk-Graphen
• Die kombinatorische Hirsch-Vermutung