Seminars
View all Seminars | Download ICal for this eventNegative-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