[Mittagsseminar TI] noon seminar: thesis defense

["László Kozma" <lkozma@zedat.fu-berlin.de>]

This is happening today:


Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Titel "Practical investigation of strict saddlepoint algorithms" ein.

Die Verteidigung findet am Dienstag, dem 24.09.2024, um 12:00 Uhr in der
Takustr. 9 im Raum 046 statt und wird auf Englisch gehalten.


Erstgutachter: Prof. Dr. László Kozma
Zweitgutachter: Prof. Dr. Wolfgang Mulzer
Betreuer: Prof. Dr. László Kozma


Mit freundlichen Grüßen
Yannis Klingele

---------------------

Abstract:
Given a n × n matrix A a strict saddlepoint is an entry a_ij that is
simultaneously the strict maximum in its row and the strict minimum in its
column. If a matrix admits a strict saddlepoint it is unique and an
algorithm proposed by Bienstock et al. showed that it can be found in O(n
log n) time. This theoretical upper bound has not been improved since
1991, until Dallant et al. recently showed an improved deterministic
running time of O(n log* n) where log* is the slowly growing iterated
logarithm function and an optimal randomized algorithm with an upper bound
running time O(n). In this thesis we implemented the proposed algorithms
by Bienstock et al. and Dallant et al. that find the strict saddlepoint of
a matrix to determine whether these algorithms are practical and their
theoretical bounds hold. To do so we are counting comparisons made between
entries of a given matrix during runtime and analyzing the results.

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