Campus Event Calendar
Event Entry
What and Who
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Alejandro Cassis
Max-Planck-Institut für Informatik - D1
AG1 Advanced Mini-Course
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 2 November 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear O(m log^8(n)log(W))- time algorithm for negative-weight SSSP, where W is an upper bound on the magnitude of the smallest negative-weight edge. In this work we improve the running time to O(m log^2(n) log(nW) log log n), which is an improvement by nearly six log-factors.
Joint work with Karl Bringmann and Nick Fischer. The paper can be found in https://arxiv.org/abs/2304.05279 and will appear in FOCS '23.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Please contact me if you need access to the passcode for the Zoom meeting.
Nidhi Rathi, 10/09/2023 14:35 -- Created document.