[Mittagsseminar TI] Fwd: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

und um 12


-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Fri, 4 Aug 2017 13:42:33 +0200
From: "Tobias Groß" <gross1989@zedat.fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit möchte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Titel "Algorithmen und Anwendungen für das Triangle Scheduling
Problem" einladen. Die Verteidigung findet am 08.08.2017 um 12 Uhr s.t. im
Raum 055 in der Takustraße 9 statt. Die Arbeit wurde von Dr. Claudia
Dieckmann betreut.

Zusammenfassung:

Das Triangle Scheduling Problem, von Dürr u.a. in [1] vorgestellt, ist ein
Spezialfall von Mixed-criticility Scheduling mit Jobs in Form
gleichschenkliger Dreiecke. Da es NP-schwer ist, kann der optimale
Zeitplan im Allgemeinen nur mittels Brute-Force-Algorithmus gefunden
werden, unter der Annahme P≠NP.

Der effiziente gierige Ansatz, jeweils das größte Dreieck in die größte
Lücke im Zeitplan zu setzen, kann in vielen Fällen die optimale Lösung
ermitteln, wie quantitative Tests mit gleich verteilt zufälligen Jobgrößen
zeigen. An den wenigen Beispielen mit nicht optimalem Ergebnis kann man
untersuchen, wann der gierige Algorithmus die falsche Entscheidung trifft.

Darüber hinaus kann mit Hilfe dynamischer Programmierung eine
(1+ε)-Approximation des optimalen Zeitplans gefunden werden. Indem die
Jobgrößen und Startzeiten vorher aufgerundet werden, reduziert sich die
Lösung dabei auf die Lösung von O(n^log(n)) vielen Teilproblemen.

In dieser Arbeit entwerfe ich die drei Algorithmen in Pseudocode und
implementiere sie in der Programmiersprache Java.

Außerdem ist das Triangle Scheduling Problem geometrisch betrachtet ein
Spezialfall des Packungsproblems in einem Rechteck und ich verallgemeinere
den Brute-Force-Algorithmus auf andere Figuren wie gleichseitige Dreiecke,
Kreise etc.

Mit freundlichen Grüßen
Tobias Groß

[1] C. Dürr, Z. Hanzálek, C. Konrad, R. Sitters, O. C. Vásquez, and G. J.
Woeginger, “The triangle scheduling problem,” CoRR, vol. abs/1602.04365,
2016. [Online]. Available: http://arxiv.org/abs/1602.04365

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature