4 papers
Tree Search With Predictions
Michael Dinitz, Bob Dong
``Algorithms with predictions'', or ``learning-augmented algorithms'', has proved to be an extremely useful paradigm for combining machine learning with traditional algorithms. One…
Approximation Algorithms for Optimal Hopsets
Michael Dinitz, Ama Koranteng, Yasamin Nazari
For a given graph , a "hopset" with hopbound and stretch is a set of edges such that between every pair of vertices and , there is a path with at most …
Light Edge Fault Tolerant Graph Spanners
Greg Bodwin, Michael Dinitz, Ama Koranteng +1
There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work h…
Binary Search with Distributional Predictions
Michael Dinitz, Sungjin Im, Thomas Lavastida +3
Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of wo…