BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260412T102716Z
UID:Seminar-dept-1183@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20240206T130000
DTEND:20240206T140000
SUMMARY:School Seminar Series
DESCRIPTION:Justin Dallant: Finding the saddlepoint faster than sorting\n\nA saddlepoint of an n×n matrix A is an entry of A that is a maximum in its row and a minimum in its column. Knuth (1968) gave several different algorithms for finding a saddlepoint. The worst-case running time of these algorithms is Θ(n^2), and Llewellyn, Tovey, and Trick (1988) showed that this cannot be improved, as in the worst case all entries of A may need to be queried.\n\nA strict saddlepoint of A is an entry that is the strict maximum in its row and the strict minimum in its column. The strict saddlepoint (if it exists) is unique, and Bienstock, Chung, Fredman, Schäffer, Shor, and Suri (1991) showed that it can be found in time O(n log n), where a dominant runtime contribution is sorting the diagonal of the matrix. This upper bound had not been improved since 1991. In this talk, I will present recent results breaking this sorting barrier.\n\n\n\nThis is based on joint work with Frederik Haagensen, Riko Jacob, László Kozma and Sebastian Wild.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1183
LOCATION:6th Floor Conference Room 605, EEE
END:VEVENT
END:VCALENDAR