BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UC Irvine Donald Bren School of Information & Computer Sciences - ECPv6.3.4//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:UC Irvine Donald Bren School of Information & Computer Sciences
X-ORIGINAL-URL:https://ics.uci.edu
X-WR-CALDESC:Events for UC Irvine Donald Bren School of Information & Computer Sciences
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20250309T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20251102T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20250418T110000
DTEND;TZID=America/Los_Angeles:20250418T120000
DTSTAMP:20260306T185358
CREATED:20250407T220117Z
LAST-MODIFIED:20250407T220202Z
UID:24848-1744974000-1744977600@ics.uci.edu
SUMMARY:Beating Bellman-Ford: Faster Single-Source Shortest Paths with Negative Weights
DESCRIPTION:Abstract: Shortest-path problems concern finding shortest routes through a network or graph. A common application of shortest paths in our daily lives is computing driving directions\, but graphs and shortest paths have wider usage. Perhaps the best studied version of the problem is the so-called single-source shortest-path (SSSP) problem. Here the input comprises (1) a directed graph with weights on edges (modeling time\, distance\, cost\, etc.)\, and (2) a specified starting or source vertex. The goal is to find shortest paths from the source to all other vertices in the graph. This talk considers the most general version of the problem\, where the weights on edges can be arbitrary real numbers\, including both positive and negative numbers. \nThe classical solution for general weights\, often called the Bellman-Ford algorithm\, was first published in the 1950s. The Bellman-Ford algorithm is simple and easy to implement\, but it is slow. There has thus been significant effort in producing faster algorithms\, but those improvements all involve restricting the problem in some way. For example\, there are faster algorithms for acyclic graphs\, planar graphs\, nonnegative weights\, and integer weights. The general case of real weights on arbitrary directed graphs\, however\, remains a challenge. Despite the fact that Bellman-Ford dates back to the 1950s\, no asymptotically faster algorithms had been discovered. \nThis talk presents the first asymptotically faster SSSP algorithm for real edge weights. This work received a best paper award at the 2024 ACM Symposium on Theory of Computing (STOC). \nBio: Jeremy Fineman is a Professor and the Wagner Chair of Computer Science at Georgetown University. His main research interest is in algorithm design and analysis\, with a focus on data structures\, parallel algorithms\, memory-efficient algorithms\, and scheduling. He received his Ph.D. from MIT in 2009 and did a postdoc at CMU before starting at Georgetown in 2011.
URL:https://ics.uci.edu/event/beating-bellman-ford-faster-single-source-shortest-paths-with-negative-weights/
LOCATION:Donald Bren Hall\, Irvine\, CA\, 92697\, United States
ATTACH;FMTTYPE=image/jpeg:https://ics.uci.edu/wp-content/uploads/2025/04/Jeremy_Fineman_edit.jpg
END:VEVENT
END:VCALENDAR