APPROXIMATING GRAPH PROBLEMS: THE OLD AND THE NEW

Speaker: Grigory Yaroslavtsev , Brown

Date: Wednesday, February 19, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Ilya Razenshteyn , TOC, CSAIL, MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/521

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@lists.csail.mit.edu , compalgsem@lists.csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Holly A Jones at Wednesday, February 12, 2014 at 3:53 PM.