Event
Advanced Networks Colloquium: Iraj Saniee, "Fast approximation algorithms for p-center computation"
Friday, April 8, 2016
11:00 a.m.
1146 AV Williams Building
Kim Edwards
kedwards@umd.edu
The Advanced Networks Colloquium
Fast approximation algorithms for p-center computation in large-scale informational networks
Iraj Saniee
Head of the Mathematics of Networks and Systems Research Department
Bell Laboratories, Nokia
Roundtable: Thursday, April 7, 2:00 p.m., 1146 AV Williams
Abstract
After some preliminary definitions, I briefly document our investigations that show ‘informational networks’ typically have very small hyperbolic constants. This motivates the rest of the talk, which is as follows. We provide a quasi-linear time algorithm for the p-center problem with an additive error not exceeding 3 times a network's hyperbolic constant. Specifically, for the graph G = (V,E) with n vertices, m edges and hyperbolic constant delta, we construct an algorithm for the p-center computation in time O(p + 1)(delta+1)(n + m)log(n)) with radius r(p) + delta when p =3, where r(p) is the optimal radius of the p-center. Prior work had identified p centers with accuracy r(p) + delta but with time complexity O((n^3 log n + n^2 m) log(diam(G))) which is infeasible for large graphs, that is, graphs with 10K or more nodes.
This is joint work with Katherine Edwards and Sean Kennedy.
Biography
Iraj Saniee is Head of the Mathematics of Networks and Systems Research Department at Bell Laboratories, Nokia at Murray Hill, NJ. He received the Ph.D. degree in operations research and control theory and the M.A. (Hon.) and B.A. (Hon.) degrees in mathematics, all from the University of Cambridge. His current recent research interests are in distributed optimization for resource allocation in communication systems and geometric properties of informational networks. He has been a member of IEEE, INFORMS and IFIP WG 7.3 in Computer Performance Modeling and Analysis and also a past member of the American Mathematical Society, Society for Industrial and Applied Mathematics, and a past Chair of the Telecommunication Section of INFORMS. He recently completed a 10-year term on the Editorial Board of Operations Research. In the past decade. In the past decade, Dr. Saniee has been the PI of multiple AFOSR and NIST grants related to geometry of information networks. He has served on program committees of numerous IEEE and INFORMS conferences and workshops.
