Yannis Klingele:
Practical investigation of strict saddlepoint algorithms
Kurzbeschreibung
Given a n × n matrix A a strict saddlepoint is an entry aij 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.