Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2025
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 …
cs.DS2025
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…