Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Speaker:Stephan Friedrichs
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 19 November 2015
Duration:30 Minutes
Building:E1 4
A \emph{metric tree embedding} of expected \emph{stretch $\alpha$} maps a weighted $n$-node graph $G = (V, E, \omega)$ to a weighted tree $T = (V_T, E_T, \omega_T)$ with $V \subseteq V_T$ such that $\operatorname{dist}(v, w, G) \leq \operatorname{dist}(v, w, T)$ and $\E[\operatorname{dist}(v, w, T)] \leq \alpha \operatorname{dist}(v, w, G)$ for all $v, w \in V$. Such embeddings are highly useful for designing fast approximation algorithms, as many hard problems are easy to solve on tree instances. However, to date the best parallel $\operatorname{polylog} n$ depth algorithm that achieves an asymptotically optimal expected stretch of $\alpha \in \operatorname{O}(\log n)$ requires $\operatorname{\Omega}(n^2)$ work and requires a metric as input.

In this paper, we show how to achieve the same guarantees using $\operatorname{\tilde{O}}(m^{1+\epsilon})$ work, where $m$ is the number of edges of $G$ and $\epsilon > 0$ is an arbitrarily small constant. Moreover, one may reduce the work further to $\operatorname{\tilde{O}}(m + n^{1+\epsilon})$, at the expense of increasing the expected stretch $\alpha$ to $\operatorname{O}(\epsilon^{-1} \log n)$. Our main tool in deriving these parallel algorithms is an algebraic characterization of a generalization of the classic Moore-Bellman-Ford algorithm. We consider this framework, which subsumes a variety of previous "Moore-Bellman-Ford-flavored" algorithms, to be of independent interest.

Name(s):Stephan Friedrichs
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Stephan Friedrichs, 11/09/2015 02:20 PM -- Created document.