Arbeitsgruppe Algorithmen und Komplexität

Themenvorschläge

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 KleinProf. 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