[Mittagsseminar TI] SPECIAL Mittagsseminar on FRIDAY, September 20th

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

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

            Freitag, 20. September 2024, 12:00 Uhr, SR 046, Takustraße 9
            Tony Wirth (Sidney)
            zum Thema: Coverage Problems in Streams

Abstract

Set Cover and Maximum-k-Coverage are fundamental NP-hard computational 
problems. The greedy algorithm for set selection is known to be 
effective and in some sense optimal. However, realizing the  greedy 
approach on streamed data (indeed on data in external memory) is not 
obvious. In this presentation, I recap several of my works on coverage 
in streams, including multipass streams, random-order streams and 
dynamic streams, some lower bounds, and in practical approaches to 
accelerate the principled application of greedy. This includes 
collaborations with Graham Cormode, Howard Karloff, Amit Chakrabarti, 
Stephen Jaud, Farhana Choudhury, and Rowan Warneke. Time permitting, I 
will talk to my latest work on Maximum Unique Coverage: an elegant variant.



Bio

Since April, Tony Wirth has been Professor in the School of Computer 
Science at The University of Sydney. Prior to this, he had a 19-year 
career in the School of Computing and Information Systems at Melbourne, 
also his undergraduate institution. His PhD was at Princeton, advised by 
Moses Charikar. Tony’s interests are several, and include: approximation 
algorithms for graph problems, specifically correlation clustering; 
streaming problems, specifically max coverage and set cover; search with 
errors; and compression and search in text archives and streams.

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