Timezone: »

 
Poster
Faster Fundamental Graph Algorithms via Learned Predictions
Justin Chen · Sandeep Silwal · Ali Vakilian · Fred Zhang

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #617
in Poster Session 3 »

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. Comput., 1995);(iii) We provide a general reduction-based framework for learning-based graph algorithms, leading to new algorithms for degree-constrained subgraph and minimum-cost 0-1 flow, based on reductions to bipartite matching and the shortest path problem.Finally, we give a set of general learnability theorems, showing that the predictions required by our algorithms can be efficiently learned in a PAC fashion.

Keywords: OPT: Discrete and Combinatorial Optimization · Theory · MISC: Scalable Algorithms
[ Slides]  [ Poster]  [ Paper PDF] 

Author Information

Justin Chen (MIT)
Sandeep Silwal (MIT)
Ali Vakilian (Toyota Technological Institute at Chicago)
Fred Zhang (UC Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors