[Colloquium] Talks at TTIC: Grigory Yaroslavtsev, Brown University, ICERM
Dawn Ellis
dellis at ttic.edu
Tue Feb 11 12:22:41 CST 2014
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/20140211/64cf628f/attachment-0001.htm
More information about the Colloquium
mailing list