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.