Seminars

View all Seminars  |  Download ICal for this event

Negative-Weight Single-Source Shortest Paths in Near-linear Time

Series: Bangalore Theory Seminars

Speaker: Danupon Nanongkai Max Planck Institute for Informatics Germany

Date/Time: Sep 30 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(m log^8(n) log W) time when edge weights are integral and can be negative and are >=-W. This essentially resolves the classic negative-weight SSSP problem. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools.

Organizers note: The talk is based on a paper that is the co-winner of the best paper award at FOCS 22.

For more details please visit: Link

Microsoft teams link:

Link



Hosts: Rahul Madhavan and Rameesh Paul