APPROXIMATING GRAPH PROBLEMS: THE OLD AND THE NEW
Date: Wednesday, February 19, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn , TOC, CSAIL, MIT
Contact: Rebecca Yadegar, firstname.lastname@example.org
Relevant URL: http://toc.csail.mit.edu/node/521
Speaker URL: None
email@example.com , firstname.lastname@example.org
TALK: APPROXIMATING GRAPH PROBLEMS: THE OLD AND THE NEW
In this talk I will discuss new approximation algorithms for multiple classes of classical problems in large graphs. Ubiquity of graphical data makes it possible to apply such algorithms to remove redundancy in distributed systems, cut their costs, simplify the structure of a complicated network, cluster a big set of data points, identify common objects on two large images, etc. Abstract: For the most general case of directed graphs I will focus on sparsification with distance and connectivity preserving guarantees (directed spanners and Steiner forests). For planar graphs I will discuss algorithms for a class of problems, which have costs associated with nodes of the graph. I will also introduce new theoretical ideas applicable to modern massive parallel computational models such as MapReduce. I will explain how to design sketching techniques for geometric graphs in Euclidean space, which allow to compute approximate minimum spanning tree and minimum cost bichromatic matching (Earth Mover's Distance) for huge graphs in constant number of rounds of communication and almost linear time per machine. This talk is based on multiple papers by the speaker in collaboration with Alexandr Andoni, Piotr Berman, Arnab Bhattacharyya, Krzysztof Onak, Aleksandar Nikolov, Konstantin Makarychev and Sofya Raskhodnikova.
Created by Holly A Jones at Wednesday, February 12, 2014 at 3:53 PM.