BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20131027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20140330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.6770.field_data.0@www.glad.uniroma1.it
DTSTAMP:20260405T093540Z
CREATED:20131123T163324Z
DESCRIPTION:We give algorithms for geometric graph problems in modern paral
 lel models such as MapReduce. Our algorithms produce approximate solutions
  for problems such as Minimum Spanning Tree (MST) and Earth-Mover Distance
  (EMD). Provided the underlying set of points lies in a space of constant 
 dimension\, only a constant number of rounds is necessary for producing a 
 solution\, while the total amount of space and communication remains linea
 r in the size of the data. In contrast\, for general graphs\, achieving th
 e same result for MST (or even connectivity) remains a challenging open pr
 oblem\, despite drawing significant attention in recent years.Our algorith
 mic framework has implications beyond the MapReduce model. For example\, i
 t yields a new algorithm for approximating EMD in the plane in near-linear
  time n^(1+o(1)). We note that while recently Sharathkumar and Agarwal (ST
 OC 2012) have developed a near-linear time algorithm for (1+epsilon)-appro
 ximating EMD\, our approach is fundamentally different and also solves the
  transportation (cost) problem\, raised as an open question in their work.
 Joint work with Alexandr Andoni (Microsoft Research)\, Aleksandar Nikolov 
 (Rutgers University)\, and Grigory Yaroslavtsev (Brown University).
DTSTART;TZID=Europe/Paris:20131127T140000
DTEND;TZID=Europe/Paris:20131127T140000
LAST-MODIFIED:20131126T141251Z
LOCATION:DIAG - Via Ariosto 25\, Aula Magna
SUMMARY:Krzysztof Onak (IBM TJ Watson Research): Parallel Algorithms for Ge
 ometric Graph Problems - Krzysztof Onak (IBM TJ Watson Research)
URL;TYPE=URI:http://www.glad.uniroma1.it/node/6770
END:VEVENT
END:VCALENDAR