Timezone: »

 
Poster
Speeding Up Bellman Ford via Minimum Violation Permutations
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #312
in Poster Session 1 »

The Bellman-Ford algorithm is a basic primitive for computing single source shortest paths in graphs with negative weight edges. Its running time is governed by the order the algorithm examines vertices for iterative updates on the value of their shortest path. In this work we study this problem through the lens of 'Algorithms with predictions,' and show how to leverage auxiliary information from similar instances to improve the running time. We do this by identifying the key problem of Minimum Violation Permutations, and give algorithms with strong approximation guarantees as well as formal lower bounds. We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice.

[ PDF] 

Author Information

Silvio Lattanzi (Google)
Ola Svensson (EPFL)
Sergei Vassilvitskii (Google)

More from the Same Authors