Gregory Schwartzman visits us for a week in Vienna after DISC!
Abstract:
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 + ε)-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 ε.
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 + ε)-approximation algorithm for the maximum weight matching problem. This improves upon the currently best known approximation ratio of (4 + ε). Our algorithm uses O(n log^2 n) space for constant values of ε.
This talk will be self contained.
Based on joint works with Reuven Bar-Yehuda, Keren Censor-Hillel, and Ami Paz
Bio:
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.
