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:Approximating APSP without Scaling
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 16 April 2019
Duration:30 Minutes
Building:E1 4
Zwick's (1+eps)-approximation algorithm for the All Pairs Shortest Path problem runs in time O(n^omega / eps * log W), where omega <= 2.373 is the exponent of matrix multiplication and W denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound.

We study whether the factor log W can be avoided, that is, whether APSP and related problems admit "strongly polynomial" approximation schemes, whose running time is independent of W. For APSP on undirected graph as well as for several graph characteristics on directed or undirected graphs we remove the log W-factor from Zwick's running time. For APSP on directed graphs, we design a strongly polynomial approximation scheme in time O(n^{(omega + 3)/2} / eps). We also explain why this has a worse exponent than omega: Any improvement over our exponent (omega + 3)/2 would improve the best known algorithm for MinMaxProduct. In fact, we prove that approximating directed APSP and exactly computing the MinMaxProduct are equivalent.

Joint work with Marvin Künnemann and Karol Wegrzycki.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 04/15/2019 06:39 PM
Last modified:
Uwe Brahm/MPII/DE, 04/16/2019 07:01 AM
  • Karl Bringmann, 04/15/2019 06:39 PM -- Created document.