[Colloquium] REMINDER: Talks at TTIC: Grigory Yaroslavtsev, Brown University, ICERM

[Dawn Ellis]

When:     Monday, February 17th at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Speaker:  Grigory Yaroslavtsev, Brown University, ICERM

Title:       "Approximating Graph Problems: The Old and the New"

Abstract:

"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.

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."

Host: Julia Chuzhoy, cjulia at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140214/a1bfc08e/attachment.htm