Arbeitsgruppe Algorithmen und Komplexität

Abschlussarbeiten

Dissertationen

 

Master- und Diplomarbeiten

 

Masterarbeiten

  • Ein experimenteller Vergleich verschiedener theoretischer Algorithmen für das Feedback Vertex Set Problem;

    Patrick Lund, 2017

  • Algorithmen für Rucksackprobleme mit Kardinalitätsbeschränkung;

    Fridtjof Schulte Steinberg, 2017

  • Online Strip Packing with Polynomial Migration;

    Leon Ladewig, 2016

  • An Algorithm for an Online Pickup and Delivery Problem;

    Kevin Prohn, 2016

  • Special Cases of the Restricted Assignment Problem;

    Lars Rohwedder, 2016

  • Scheduling auf identischen Maschinen mit einer geteilten Ressource;

    Malin Rau, 2015

  • Optimierung von Spielplänen auf mehreren Feldern;

    Ralf-Tobias Diekert, 2014

  • Approximationsalgorithmen für das Färben von Unit-Disk-Graphen;

    Marcin Pal, 2014

  • Entwicklung praxistauglicher Algorithmen für die Tourenplanung mobiler Mitarbeiter;

    Niklas Paulsen, 2014

  • Robust Bin Packing - Theory and Praxis;

    Sebastian Berndt, 2012

  • Unterstützung von Scheduling-Entscheidungen mit Prognosen der Passagiernachfrage;

    Thorsten Ehlers, 2012

  • Approximation Algorithms for Scheduling Problems;

    Loredana Casiana Balaj (geb. Baba), 2011

  • Approximation Algorithms for Multicast Networks' Congestion Problem;

    Narendran Vaideeswaran, 2005

 

Diplomarbeiten

  • Kombinatorische Algorithmen des Dial-A-Ride-Problems;

    Steven Schwarz, 2015

  • Algorithmen für das Dial-a-Ride Problem mit Transfers;

    Jan Bielke, 2013

  • Strip Packing mit konstanter Anzahl von Itemtypen;

    Katja Haase, 2013

  • Implementation of Multiple Strip Packing and Scheduling Parallel Jobs in Platforms;

    Carolin Town, 2013

  • Approximative Algorithmen für geometrische Schnittgraphen;

    Rachid El Araari, 2008

  • Approximation schemes for scheduling on unrelated parallel machines;

    Tim Hartnack, 2008

  • Approximation Algorithms for Two-Dimensional Geometrical Knapsack;

    Lars Prädel, 2008

  • Sportligaplanung und 3-Index-Assignment-Probleme;

    Uwe-Nicolas Schmidt, 2007

  • Implementation of Algorithms for Packing and Covering Problems;

    Stefan Ludwig, 2006

  • Design and Analysis of Approximation Algorithms for Certain Scheduling Problems;

    Ulrich Michael Schwarz, 2006

  • Approximative Algorithmen zur Lösung spezieller linearer Programme;

    Matthias Druske, 2005

  • Theoretische Aufarbeitung und praktische Implementierung des Algorithmus von Agrawal, Kayal und Saxena;

    Susanne Burfeind, 2005

  • Approximative Algorithmen für Rucksackprobleme;

    Florian Diedrich, 2004

  • Geradenfärbung von Hypergraphen - Über eine Vermutung von Erdös, Faber und Lovász;

    Ralf Thöle, 2004

Bachelor- und Studienarbeiten

   

Bachelorarbeiten

  • Kombinatorische Hirsch Conjecture;

    Maximilian Reinhart, 2017

  • Multikritielle Gebietseinteilung und effiziente Tourenplanung;

    Johann Philipp Doose, 2016

  • Periodic Maintenance Minimization Problem;

    Florian Fedrau, 2016

  • FDDARP, Eine Many-to-One Dial-a-Ride Variante;

    Kilian Grage, 2016

  • Genetische Algorithmen für das zeitabhängige Travelling Salesman Problem;

    Morten Jessen, 2016

  • Algorithmen zur Zuweisung von Seminarplätzen;

    Sandra Ladewig, 2016

  • Tourenplanung im Umfeld eines Fahrradlieferdienstes;

    Bernd Strehl, 2016

  • Untersuchung des Integrality Gap beim Restricted Assignment Problem;

    Stephan Bogs, 2015

  • A Hybrid Approach to the General High School Timetabling Problem;

    Valentin Dreismann, 2015

  • Scheduling mit Maschinentypen;

    Lars Sebastian Hauser, 2015

  • Vergleich von Heuristiken für Scheduling auf uniformen Maschinen;

    Birger Hein, 2015

  • Stundenplanerstellung;

    Susanne Koch, 2015

  • Minimizing Average Weighted Completion Time for Scheduling Parallel Multiprocessor Tasks on a Variable Number of Machines;

    Florian Mai, 2015

  • Robustes Online-Scheduling auf uniformen Maschinen;

    Nils Peter Maretzke, 2015

  • Implementierung und Vergleich von approximativen Algorithmen für das 2D Strip Packing;

    Peter Milster, 2015

  • Restricted Assignment mit wenigen Ausführungszeiten;

    Christian Böteführ, 2014

  • Geografische Dekomposition für das PESP in Anwendung auf Zugfahrpläne;

    Leon Ladewig, 2014

  • Produktionsplanung in der Holzwirtschaft;

    Alexander Lauenroth, 2014

  • Gewinnteamermittlung und die magische Punktzahl;

    Tim Mahlstedt, 2014

  • Strip-Packing mit konstant vielen Itemtypen;

    Philipp Millar, 2014

  • Implementation und Test eines moderat-exponentiellen Algorithmus für Scheduling auf uniformen Maschinen;

    Erik Theesen, 2014

  • Scheduling on Identical Machines with a Bounded Number of Different Production Times;

    Till Blume, 2013

  • Approximative Algorithmen für das Steinerbaumproblem;

    Patrick Lund, 2013

  • Approximative Algorithmen für Scheduling auf identischen Maschinen;

    Kevin Prohn, 2013

  • Fairness in Round Robin Turnieren;

    Katharina Rahf, 2013

  • Efficient Optimization of School Timetables;

    Stefan Röpstorff, 2013

  • Effiziente Lösungen für das Delay Management Problem;

    Christian Claus Wiechmann, 2013

  • Optimierung des Transportproblems basierend auf Simulated Annealing;

    Santje Finke, 2012

  • Robust Approximation Schemes for Online Bin Packing;

    Sebastian Berndt, 2010

  • Scheduling with Migration;

    Thorsten Ehlers, 2010

  • Implementation of Thorup's Linear Time Algorithm for Undirected Single-Source Shortest Paths with Positive Integer Weights;

    Nick Prühs, 2010

  • On Approximative Algorithms for a Three-Dimensional Orthogonal Knapsack Problem;

    Henning Thomas, 2006

 

Studienarbeiten

  • Approximation Algorithms for Geometric Intersection Graphs;

    Rashid El Araari, 2007

  • Studienarbeit zum Thema Reverse-Fit;

    Lars Prädel, 2007

  • Scheduling Malleable Tasks with Precedence Constraints: An Implementation;

    Ulrich Michael Schwarz, 2004

  • Implementation of Approximation Algorithms for Strip-Packing;

    Florian Diedrich, 2003

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 Malin Rau & 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 Sebastian Berndt & 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 Lars Rohwedder & 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