CT-Talk mit Gregory Schwartzman

22.10.2019 11:30 - 12:30

Am 22.10.2019 hält Gregory Schwartzman auf Einladung der Forschungsgruppe Communication Technologies einen Talk zum Thema „The local-ratio technique in environments with uncertainty“. Die Fakultät für Informatik lädt alle Interessierten herzlich dazu ein!


This talk will focus on adaptations of the local-ratio technique to environments with uncertainty. We show how to adapt this classical technique to the distributed and semi-streaming environments, achieving state of the art approximation algorithms for vertex cover and maximum matching. The field of distributed graph algorithms deals with solving graph problems in a network (graph) of independent agents while minimizing the amount of communication between nodes. We present a fast (2 + E)-approximation algorithm for weighted vertex cover. Due to a known lower bound, the number of communication rounds our algorithm achieves is tight for all constant values of E. In the semi-streaming model there is a graph for which we know the vertex set, but whose edges arrive in a stream, and at the end of the stream we must output a solution to some graph problem. This model was inspired by the recent surge in big-data, thus we assume we do not have enough space to store all of the graph edges. The algorithm must provide an answer while not exceeding a memory usage of O(n polylog(n)), where n is the number of vertices. We present a simple deterministic single-pass (2 + E)-approximation algorithm for the maximum weight matching problem. This improves upon the currently best known approximation ratio of (4 + E). Our algorithm uses O(n log^2 n) space for constant values of E. This talk will be self contained. Based on joint works with Reuven Bar-Yehuda, Keren Censor-Hillel, and Ami Paz


Gregory Schwartzman received his PhD from the Technion, Israel, in 2017. Since then he has been a postdoc at the National Institute of Informatics, Tokyo. His research deals with designing fast algorithms for fundamental graph problems in environments with uncertainty, specifically distributed algorithms. His works were awarded with the best student paper award at PODC 2016 and best paper and best student paper award at SODA 2017.


CT-Talk mit Gregory Schwartzman
Wann: DI, 22.10.2019, 11:30
Wo: SR2 | Währinger Straße 29, 1090 Wien

Forschungsgruppe CT

Seminarraum 2 (SR2) W29

Währinger Straße 29
1090 Wien