[Mittagsseminar TI] Fwd: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit

[Katharina Klost <katharina.klost@fu-berlin.de>]

Tommorow in the noon seminar, potentionally in German.


-------- Weitergeleitete Nachricht --------
Betreff: [Ml-iwimi-mi] Einladung zur Verteidigung meiner Bachelorarbeit
Datum: Sun, 16 Jul 2023 22:15:16 +0200
Von: Philipp Walter <zuramm@zedat.fu-berlin.de>
An: i-studi@inf.fu-berlin.de
Kopie (CC): i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, 
maria.koekenhoff@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie zu der Verteidigung meiner Bachelorarbeit
mit dem Titel "Experimental Evaluation of Algorithms for Long Plane Trees"
ein.

Die Verteidigung findet am Donnerstag, den 20.07.2023, um 12:00 Uhr im
Seminarraum 055, Takustr. 9 statt.

Erstgutachterin: Dr. Katharina Klost
Zweitgutachter: Prof. Dr. Wolfgang Mulzer

Mit freundlichen Grüßen
Philipp Walter

Abstract: Longest planar spanning trees are thought to be an NP-hard task.
One approach to such problems is to relax the solution’s criteria. This
can be achieved by identifying solutions that are not necessarily the
longest spanning tree but are planar. This paper investigates the lower
bound of the approximation factor of algorithms producing planar spanning
trees. We analyze the algorithm proposed in Cabello et al. (2021). The
algorithm finds AB trees that improve star graphs. The star is a simple
graph proposed by Alon et al. (1993), where one point is connected to
every other point. The AB tree algorithm attempts to improve the star by
adding zig-zag edges, which increases the total length. To analyze the
approximation factors, we implement four algorithms: the aforementioned AB
tree algorithm, a brute force algorithm for the longest planar spanning
tree, a longest spanning tree algorithm, and a specialized algorithm for
convex point sets. A genetic algorithm was used to find point sets with
low approximation factors programmatically. The brute force algorithm
implementation performed poorly and was only utilized for point sets of no
more than 10 points. We analyzed point sets with approximation factors of
less than 0.9. The genetic algorithm’s output has an approximation factor
of 0.9 as well. The sets with low approximation factors are very elongated
point sets, particularly ellipsoid forms. In this work, the lowest
approximation factor determined is 0.877. Our analysis finds a more overly
stretched graph results in an even lower approximation factor.

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