BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20140309T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20131103T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20220520T063657Z
UID:bf9669b4-0ade-4aa9-bc6d-9b5c98b757c9
DTSTART;TZID=America/New_York:20140219T160000
DTEND;TZID=America/New_York:20140219T170000
CREATED:20140212T155322
DESCRIPTION:In this talk I will discuss new approximation algorithms for mu
ltiple classes of classical problems in large graphs. Ubiquity of graphica
l data makes it possible to apply such algorithms to remove redundancy in
distributed systems\, cut their costs\, simplify the structure of a compli
cated network\, cluster a big set of data points\, identify common objects
on two large images\, etc. Abstract: For the most general case of directe
d graphs I will focus on sparsification with distance and connectivity pre
serving guarantees (directed spanners and Steiner forests). For planar gra
phs I will discuss algorithms for a class of problems\, which have costs a
ssociated with nodes of the graph. I will also introduce new theoretical i
deas applicable to modern massive parallel computational models such as Ma
pReduce. I will explain how to design sketching techniques for geometric g
raphs in Euclidean space\, which allow to compute approximate minimum span
ning tree and minimum cost bichromatic matching (Earth Mover's Distance) f
or huge graphs in constant number of rounds of communication and almost li
near time per machine. This talk is based on multiple papers by the speake
r in collaboration with Alexandr Andoni\, Piotr Berman\, Arnab Bhattachary
ya\, Krzysztof Onak\, Aleksandar Nikolov\, Konstantin Makarychev and Sofya
Raskhodnikova.
LAST-MODIFIED:20140212T155505
LOCATION:32-G575
SUMMARY:APPROXIMATING GRAPH PROBLEMS: THE OLD AND THE NEW
URL:https://calendar.csail.mit.edu/events/124801
END:VEVENT
END:VCALENDAR