Faster Fundamental Graph Algorithms via Learned Predictions

Understand

We consider the question of speeding up classic graph algorithms with machine-learned predictions.

• In this model, algorithms are furnished with extra advice learned from past or similar instances.
• Given the additional information, we aim to improve upon the traditional worst-case run-time guarantees.
• Our contributions are the following: (i) We give a faster algorithm for minimum-weight bipartite matching via learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley and Vassilvitskii (NeurIPS, 2021); (ii) We extend the learned dual approach to the single-source shortest path problem (with negative edge lengths), achieving an almost linear runtime given sufficiently accurate predictions which improves upon the classic fastest algorithm due to Goldberg (SIAM J.