Agenda

Speaker: Geppino Pucci, University of Padova

Abstract
We present a space and time efficient practical parallel algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. The core of the algorithm is a weighted graph decomposition strategy generating disjoint clusters of bounded weighted radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; moreover, for important practical classes of graphs, it runs in a number of rounds asymptotically smaller than those required by the natural approximation provided by the state-of-the-art $\Delta$-stepping SSSP algorithm, which is its only practical linear-space competitor in the aforementioned computational scenario. We complement our theoretical findings with an extensive experimental analysis on large benchmark graphs, which demonstrates that our algorithm attains substantial improvements on a number of key performance indicators with respect to the aforementioned competitor, while featuring a similar approximation ratio (a small constant less than 1.4, as opposed to the polylogarithmic theoretical bound). (Joint work with Matteo Ceccarello, Andrea Pietracaprina, and Eli Upfal based on papers appeared at ACM SPAA’15 and IEEE IPDPS’16.)

Bio sketch
Geppino Pucci received the Laurea summa cum laude (1987) and the Ph.D. degree (1993) both in Computer Science from the University of Pisa, Italy. From 1988 to 1990 he was a Research Associate at the Computing Laboratory of the University of Newcastle-upon-Tyne, United Kingdom, where he conducted research in software reliability modelling. From 1990 to 1991 he was a visiting graduate student at the International Computer Science Institute, Berkeley, California, upon invitation of the institute and under the supervision of Professor Richard Karp. In 1992, he joined the Department of Electrical Engineering and Computer Science (DEI) of the University of Padova, Italy, as an Assistant Professor. On leave from DEI, he returned to Berkeley in 1993 as a postdoctoral fellow. In 1996, he spent the Summer Semester at Cornell University, Ithaca, NY as a visiting professor and course instructor. Since October 2001, he has been a Full Professor of Computer Science at DEI.​