Incremental Approximate Single-Source Shortest Paths with Predictions

Aidin Niaparast; Benjamin Moseley; Helia Niaparast; Samuel McCauley; Shikha Singh

REVIEW 2 major objections 4 minor 1 cited by

Incremental Approximate Single-Source Shortest Paths with Predictions

T0 review · 2 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that a prediction of the edge insertion order lets a data structure maintain $(1+\epsilon)$-approximate single-source shortest paths in incremental graphs in near-linear total time, with running time growing only linearly…

desk verdict Genuinely new offline incremental approximate SSSP result and first learned SSSP data structure; two fixable presentation-level gaps, otherwise the central arguments hold. read the letter →

arxiv 2502.08125 v1 pith:A73ZM7ZQ submitted 2025-02-12 cs.DS cs.LG

Samuel McCauley , Benjamin Moseley , Aidin Niaparast , Helia Niaparast , Shikha Singh This is my paper · ORCID

classification cs.DScs.LG MSC 68W2768W2568R1068Q25

keywords algorithmswithpredictionslearning-augmentedincrementalgraphssingle-sourceshortestpathsdynamicgraphapproximationpredictionerrorrecursivedecomposition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to show that a prediction of the edge arrival order can break the high worst-case update cost of maintaining approximate shortest paths in an incremental graph. Its central claim is a learned data structure that maintains $(1+\epsilon)$-approximate distances from a source in total time $\tilde{O}(m\eta \log W/\epsilon)$, where $\eta$ is the prediction error, with the stronger refinement $\tilde{O}(m\cdot\min_\tau\{\tau+|\mathrm{HIGH}(\tau)|\}\log W/\epsilon)$. This running time is near-linear when predictions are good, degrades smoothly with error, and never falls behind the best offline algorithm by more than logarithmic factors, which the authors call an "ideal" learned algorithm. As an offline building block, the paper also establishes that the incremental approximate single-source shortest-path problem can be solved from scratch in worst-case time $O(m\log(nW)\log^3 n\log\log n/\epsilon)$. If correct, this is the first learned data structure for a central graph problem, and the offline result is of independent interest.

What carries the argument

The load-bearing device is a recursion tree over time: the sequence of edge insertions is split in half recursively, and each subproblem $[\ell,r]$ is handled by rounding every estimated distance up to a bucket boundary $(1+\epsilon/\log m)^i$ and running Dijkstra only on the subgraph of "alive" vertices, that is, vertices whose bucket changes between the endpoints of the interval. A vertex that keeps its bucket across an interval is "dead" and is omitted, with its known rounded distance used as a weighted edge from the source. The key charging argument (Lemma 2) bounds the total number of alive edges over all subproblems by $O(m\log(nW)\log^2 m/\epsilon)$, giving the offline running time. In the online setting, the algorithm updates the predicted sequence as each edge arrives and rebuilds exactly the subproblems whose midpoint lies between an edge's predicted and actual position; Lemma 6 bounds the number of such "jumps" over any position by $\tau+2|\mathrm{HIGH}(\tau)|$, which yields the final time bound.

What would settle it

Run the offline algorithm on a family of weighted directed graphs with carefully staggered edge weights, and count the total number of alive edges across all recursive subproblems; if for any $n,m,\epsilon$ the count exceeds $C m\log(nW)\log^2 m/\epsilon$ for a fixed constant $C$, the central charging lemma is false. A more targeted test: construct a graph where a single vertex's shortest distance decreases in tiny increments that each cross a bucket boundary many times, and check whether the number of bucket changes per vertex is indeed $O(\log(nW)\log m/\epsilon)$ and whether each change is charged to only one subproblem per level.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 2: given a prediction $\hat{\sigma}$ of the edge insertion sequence, an online algorithm maintains a $(1+\epsilon)$-approximate single-source shortest path at every time step, for arbitrary weighted directed graphs, with total running time $\tilde{O}(m\cdot\min_\tau\{\tau+|\mathrm{HIGH}(\tau)|\}\cdot\log W/\epsilon)$, where $\mathrm{HIGH}(\tau)$ is the set of edges whose predicted arrival time differs from its actual arrival time by more than $\tau$. This yields a bound of $\tilde{O}(m\eta\log W/\epsilon)$ in terms of maximum edge-wise error $\eta$, and $\tilde{O}(m\cdot\mathrm{Edit}(\sigma,\hat{\sigma})\log W/\epsilon)$ in terms of the edit distance between the true and predicted sequences. The paper further claims that the same techniques give an offline incremental approximate SSSP algorithm (Theorem 1) with worst-case total time $O(m\log(nW)\log^3 n\log\log n/\epsilon)$, and that the online results extend to all-pairs shortest paths with $\tilde{O}(nm\log W/\epsilon)$ preprocessing, $O(\log n)$ worst-case update time, and $O(\eta^2\log\log(nW))$ query time (Theorem 3).

Load-bearing premise

The whole bound depends on the assumption that a vertex's rounded distance estimate changes only when the true distance crosses a bucket boundary, and that charging each such change to one subproblem per recursion level also covers the cost of filtering dead edges at every subproblem.

Editorial extensions

If this is right

With perfect or near-perfect predictions, the algorithm runs in near-linear time $\tilde{O}(m\log W/\epsilon)$, matching up to logarithmic factors the cost of reading the input, which is optimal in the worst case.
Performance degrades gracefully: total time grows linearly with the prediction error $\eta$, or, more robustly, with $\min_\tau\{\tau+|\mathrm{HIGH}(\tau)|\}$, which combines a bounded number of badly misplaced edges with a bound on the displacement of all others.
The algorithm is robust in that a switch to a worst-case algorithm can bound the time even for arbitrarily erroneous predictions, so the learned guarantee never exceeds the best offline guarantee by more than logarithmic factors.
The offline incremental approximate SSSP algorithm is a new worst-case result of independent interest, beating the $n^{1-o(1)}$ amortized lower bound for exact incremental SSSP by moving to approximation.
The same recursive decomposition extends to all-pairs shortest paths, giving a learned data structure with poly-logarithmic worst-case update and query times that supports weighted graphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The bucket-rounding charging argument is essentially a distance-monotonicity argument: distances only decrease, so the number of bucket crossings per vertex is bounded. The same argument pattern could plausibly be transferred to other monotone dynamic graph problems, such as incremental reachability or minimum spanning forest, wherever approximate potentials can be bucketed.
The edit-distance error measure the paper introduces is a more forgiving measure than max edge displacement and might itself be useful as a prediction-quality parameter in other online data-structure problems.
One testable consequence: on graphs where many vertices have similar distances that decrease in lockstep, the alive-edge count should be far below the worst-case bound, so a practical implementation might be even faster than the guarantee suggests.
If the near-linear offline result is tight, it would imply that the difficulty of incremental SSSP is not incremental structure per se but exactness: approximation plus a priori knowledge of the sequence removes the polynomial hardness.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Hi,

I read the arXiv:2502.08125 paper. Short version: the central results look correct and are a real contribution, but the proofs have two spots that need patching before I'd call them complete.

The offline result (Theorem 1) is new as far as I know: an O~(m log W/epsilon) total-time algorithm for maintaining (1+epsilon)-approximate SSSP under edge insertions when the edge sequence is known in advance. The previous offline work I'm aware of is exact and has n^{1-o(1)} lower bounds. The technique—recursively splitting the timeline and only running Dijkstra on vertices whose rounded distance bucket changes, with rounding to (1+epsilon/log m) powers to control error accumulation—is non-obvious and well explained. Lemmas 1, 4, and 5 are convincing.

The learned online algorithm (Theorem 2) is the first for SSSP with predictions. The bound O~(m min_tau {tau+|HIGH(tau)|} log W/epsilon) is a good tri-criteria guarantee, and the edit-distance corollary is a nice addition. The APSP extension is mostly a black-box reuse of van den Brand's query scheme, but that's fine as a consequence.

Now the soft spots. First, Lemma 2's running-time proof omits accounting for the O(m_r) cost of iterating over alive edges at the right endpoint r when building each subproblem's midpoint graph. The proof bounds the sum of m_x over midpoints, but the filtering cost is a sum over subproblems of m_r. The stress-test note I saw flags this, and it's a real gap. It's not fatal: each r is the right endpoint of O(log m) subproblems, so the extra term is O(log m) times the midpoint sum, and the claimed O(log^3 n) already absorbs that extra log. But the proof should say this explicitly.

Second, Theorem 2's bound literally evaluates to O~(0) when predictions are perfect (tau=0 gives HIGH=empty, so min is 0). The intent is clear—the algorithm must run the offline preprocessing once—but the statement should be O~(m(1+min_tau{tau+|HIGH|}) log W/epsilon) or similar. This is a presentation bug, not a conceptual one.

Third, the 'ideal' robustness claim is achieved only by explicitly switching to a worst-case algorithm when the learned path is slow; the theorem itself doesn't contain that switch. The abstract oversells this slightly.

No circularity concerns. The self-citations are legitimate and don't carry the load. No code, but this is a theory paper.

Who's it for? Anyone working on dynamic graph algorithms or algorithms with predictions. I'd give it a serious referee. With those two patches it should be publishable.

Hope this helps.

Referee Report

2 major / 4 minor

Summary. The paper studies incremental approximate single-source shortest paths in the algorithms-with-predictions model. The main contributions are (i) an offline algorithm that, given the full edge insertion sequence in advance, builds a data structure answering (1+epsilon)-approximate distance queries for every vertex and time in total time O(m log(nW) log^3 n log log n / epsilon) (Theorem 1), and (ii) an online learning-augmented version whose total running time is O~(m * min_tau { tau + |HIGH(tau)| } log W / epsilon), where HIGH(tau) is the set of edges whose predicted arrival time differs from the true time by more than tau (Theorem 2). The online algorithm maintains the offline recursion tree, rebuilding only subproblems whose midpoint is jumped over by a mispredicted edge. The paper also extends the approach to all-pairs shortest paths with predictions (Theorem 3). The central algorithmic idea is to round distances to powers of (1 + epsilon/log m), mark vertices whose rounded distance is constant over a recursive interval as dead, and run Dijkstra only on subgraphs induced by alive vertices, charging work to bucket changes.

Significance. If the results are correct, this is the first learned data structure for incremental approximate SSSP, and the offline incremental approximate SSSP algorithm is a natural and useful building block of independent interest. The claimed guarantees are strong: consistency with the offline algorithm under perfect predictions, smooth linear degradation with prediction error, and robustness matching the best offline bound up to logarithmic factors. The paper is also careful in its error model and in separating the role of the offline algorithm as a black box. I found no circularity or fitted parameters in the analysis; the arguments are based on standard non-increasing distance properties and deterministic charging. The main proofs are detailed, but two statement-level issues need attention: an omitted accounting step in the key charging lemma of the offline algorithm, and a degenerate minimizer in the statement of the online running-time theorem. Neither issue appears fatal, but each is load-bearing enough to require a revision.

major comments (2)

[Section 4.2, Lemma 2] The proof of Lemma 2 omits the O(m_r) filtering cost. For a subproblem [l, r] with midpoint x, the algorithm finds the alive edges and vertices of G_x by iterating over the alive edges of G_r, which costs O(m_r), where m_r is the number of alive edges in subproblem r. The proof then bounds the total cost by O(log n log log m) times S = sum_x m_x, where the sum is over all subproblems x; the O(m_r) terms are not included in this summation. As written, the claimed total time of Theorem 1 does not follow. This gap is repairable: each time index r is the right endpoint of at most O(log m) subproblems in the recursion tree, and m_r is exactly the alive-edge count of the subproblem with midpoint r, so sum_{[l,r]} m_r <= O(log m) * (S + endpoint terms). Adding this step contributes one extra log m factor, which still fits inside the stated O(log^3 n) budget. The proof should explicitly supply this argument.
[Theorem 2 and Corollary 1] The running-time bound O~(m * min_tau { tau + |HIGH(tau)| } log W / epsilon) is formally degenerate when predictions are perfect. If eta = 0, then for tau = 0 we have |HIGH(0)| = 0, so the expression evaluates to O~(0), which cannot be a valid total running time for an algorithm that must read the input. The same issue propagates to Corollary 1 when eta = 0. The fix is local: minimize over positive integers tau, or write the bound as O~(m * (1 + min_{tau >= 0} { tau + |HIGH(tau)| }) log W / epsilon). This does not change the substance of the consistency claim, but the theorem as stated is not meaningful at the endpoint.

minor comments (4)

[Section 4.2, Lemma 2] The proof uses 'log m = O(log n)' to convert the charge bound. This is only true for simple graphs, where m <= n^2. If parallel edges or multi-edges are allowed, the substitution is invalid. The paper should either state explicitly that the graph is simple, or explain how redundant parallel edges are compressed in the input sequence.
[Section 4.1 and Lemma 1] The recovery step for a dead tail vertex u states that the algorithm finds the first ancestor of x where u is alive, but it does not discuss the case where no such ancestor exists (for example, a vertex whose distance is infinite throughout the interval). Such a vertex can still be the tail of an alive edge, and the edge weight is then infinite, which Dijkstra can ignore. The proof should either handle this case explicitly or state that infinite edge weights are discarded.
[Lemma 4] The proof that an un-rebuilt subproblem x has the same binary search tree in T_{t-1} and T_t is terse, particularly the assertion that dead-vertex estimates are stored in ancestors that are 'the same' in both trees. This is correct in spirit, but the induction would be easier to follow if the proof explicitly tracked the interval containing x and the fact that the edge jump does not cross any midpoint of x or its ancestors.
[Lemma 7] In the accounting for the D-array updates, the sentence 'each subproblem that gets rebuilt throughout all the edge insertions gets charged at most once' is not literally justified: a no-rebuild step can charge to the last rebuild of subproblem t even if that rebuild was already charged earlier. The bound can instead be obtained directly by summing the number of alive vertices over all subproblems, which Lemma 2's charging already controls. The text should be clarified to avoid the appearance of an unsupported amortization claim.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard properties of shortest paths (nonnegative weights, non-increasing distances) and the algorithmic construction of alive/dead vertices with bucket rounding. No parameters are fitted to data. The paper introduces no new physical or mathematical entities; the alive/dead status and prediction error are algorithmic constructs, not postulated entities.

assumptions (4)

domain assumption Edge weights are positive and bounded in [1,W]; every simple path has length at most nW.
Stated in Section 2; used to bound the number of distance buckets by O(log(nW)/epsilon) and to define W.
standard math Distances from the source are non-increasing as edges are inserted.
Used throughout Sections 3 and 4 to argue that a vertex in the same bucket at both endpoints stays in that bucket throughout the interval (e.g., Section 3.1).
standard math Standard Dijkstra's algorithm on nonnegatively weighted graphs is correct and takes O(m log n) time.
Invoked as a subroutine in Sections 4.1 and 6.
domain assumption The prediction model provides sigma_hat before any edges arrive, and all edges in the input sequence are distinct.
Assumed in Sections 2 and 5.1; needed for the jump-and-rebuild rule and for the definition of eta.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Incremental Approximate Single-Source Shortest Paths with Predictions." pith.science (2026). https://pith.science/paper/A73ZM7ZQ

@misc{pith2026250208125,
  author       = {Pith},
  title        = {Pith review of: Incremental Approximate Single-Source Shortest Paths with Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A73ZM7ZQ}},
  note         = {Machine review of arXiv:2502.08125}
}

abstract

The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing interest in leveraging predictions for designing data structures with improved beyond-worst-case running times. In this paper, we study the fundamental data structure problem of maintaining approximate shortest paths in incremental graphs in the algorithms-with-predictions model. Given a sequence $\sigma$ of edges that are inserted one at a time, the goal is to maintain approximate shortest paths from the source to each vertex in the graph at each time step. Before any edges arrive, the data structure is given a prediction of the online edge sequence $\hat{\sigma}$ which is used to ``warm start'' its state. As our main result, we design a learned algorithm that maintains $(1+\epsilon)$-approximate single-source shortest paths, which runs in $\tilde{O}(m \eta \log W/\epsilon)$ time, where $W$ is the weight of the heaviest edge and $\eta$ is the prediction error. We show these techniques immediately extend to the all-pairs shortest-path setting as well. Our algorithms are consistent (performing nearly as fast as the offline algorithm) when predictions are nearly perfect, have a smooth degradation in performance with respect to the prediction error and, in the worst case, match the best offline algorithm up to logarithmic factors. As a building block, we study the offline incremental approximate single-source shortest-paths problem. In this problem, the edge sequence $\sigma$ is known a priori and the goal is to efficiently return the length of the shortest paths in the intermediate graph $G_t$ consisting of the first $t$ edges, for all $t$. Note that the offline incremental problem is defined in the worst-case setting (without predictions) and is of independent interest.

Figures

Figures reproduced from arXiv: 2502.08125 by the authors.

**Figure 2.** An illustration of the subproblems that get rebuil [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On Incremental Approximate Shortest Paths in Directed Graphs
cs.DS 2025-02 accept novelty 6.0 of 10

New incremental (1+ε)-approximate APSP data structures for sparse digraphs reach O~(m^{3/2}n^{3/4}) deterministic and O~(m^{4/3}n^{5/6}) randomized total update time against adaptive adversaries, plus a near-linear of...

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · cited by 1 Pith paper

[1]

Sorting with predic tions

Xingjian Bai and Christian Coester. Sorting with predic tions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

work page 2023
[2]

Learning-augment ed priority queues

Ziyad Benomar and Christian Coester. Learning-augment ed priority queues. In The Thirty-eighth Annual Conference on Neural Information Processing System s, 2024

work page 2024
[3]

Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh

Ioana O. Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh. Da isy Bloom Filters. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm The ory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs ), pages 9:1–9:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentr um f¨ ur Informatik

work page 2024
[4]

Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time

Aaron Bernstein. Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time. In 2009 50th Annual IEEE Symposium on F oundations of Computer Science, pages 693–702. IEEE, 2009

work page 2009
[5]

Maintaining shortest paths under dele tions in weighted directed graphs

Aaron Bernstein. Maintaining shortest paths under dele tions in weighted directed graphs. SIAM Journal on Computing, 45(2):548–574, 2016. 17

work page 2016
[6]

Deterministic decremental SSSP and approximate min-cost ﬂow in almost-li near time

Aaron Bernstein, Maximilian Probst Gutenberg, and That chaphol Saranurak. Deterministic decremental SSSP and approximate min-cost ﬂow in almost-li near time. In 62nd IEEE Annual Symposium on F oundations of Computer Science, FOCS 2021, De nver , CO, USA, February 7-10, 2022, pages 1000–1008. IEEE, 2021

work page 2021
[7]

Near-optimal decre- mental SSSP in dense weighted digraphs

Aaron Bernstein, Maximilian Probst Gutenberg, and Chri stian Wulff-Nilsen. Near-optimal decre- mental SSSP in dense weighted digraphs. In Sandy Irani, edit or, 61st IEEE Annual Symposium on F oundations of Computer Science, FOCS 2020, Durham, NC, USA , November 16-19, 2020 , pages 1112–1122. IEEE, 2020

work page 2020
[8]

Adaptive probing policies for shortest path routing

Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. Adaptive probing policies for shortest path routing. Advances in Neural Information Processing Systems (NeurIP S), 33:8682–8692, 2020

work page 2020

Show all 47 references

[9]

Incremental single sour ce shortest paths in sparse digraphs

Shiri Chechik and Tianyi Zhang. Incremental single sour ce shortest paths in sparse digraphs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algo rithms (SODA) , pages 2463–2477. SIAM, 2021

2021
[10]

On the power of learning-augm ented BSTs

Jingbang Chen and Li Chen. On the power of learning-augm ented BSTs. arXiv preprint arXiv:2211.09251, 2022

2022 arXiv
[11]

From WiscKey to Bourbon: A learned index for log-structured merge trees

Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alag appan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. From WiscKey to Bourbon: A learned index for log-structured merge trees. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), ...

2020
[12]

Predictive ﬂows for faster ford-fulkerson

Sami Davies, Benjamin Moseley, Sergei V assilvitskii, and Y uyan Wang. Predictive ﬂows for faster ford-fulkerson. In Andreas Krause, Emma Brunskill, Kyungh yun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proc. of the 40th International Conference on ...

2023
[13]

ALEX: an updatable adaptive learned index

Jialin Ding, Umar Farooq Minhas, Jia Y u, Chi Wang, Jaeyo ung Do, Yinan Li, Hantian Zhang, Badrish Chandramouli, Johannes Gehrke, Donald Kossmann, e t al. ALEX: an updatable adaptive learned index. In Proc. 46th Annual ACM International Conference on Manageme nt of Data (SIGMO...

2020
[14]

Binary search with distributional p redictions

Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjami n Moseley, Aidin Niaparast, and Sergei V assilvitskii. Binary search with distributional p redictions. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

2024
[15]

Faster matchings via learned duals

Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjami n Moseley, and Sergei V assilvitskii. Faster matchings via learned duals. In Marc’Aurelio Ranzato, Alin a Beygelzimer, Y ann N. Dauphin, Percy Liang, and Jennifer Wortman V aughan, editors, Proc. 34th Conference on Advances...

2021
[16]

learning

Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Pu tting the “learning” into learning- augmented algorithms for frequency estimation. In Proc. 38th Annual International Conference on Machine Learning (ICML) , pages 2860–2869. PMLR, 2021

2021
[17]

Deterministic algorithms for decre- mental approximate shortest paths: Faster and simpler

Maximilian Probst Gutenberg and Christian Wulff-Nils en. Deterministic algorithms for decre- mental approximate shortest paths: Faster and simpler. In S huchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 20 20, Salt Lake City, UT, USA...

2020
[18]

Sublinear-time decremental algorithms for single-source reachability and shortest pa ths on directed graphs

Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Sublinear-time decremental algorithms for single-source reachability and shortest pa ths on directed graphs. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 674–683, 2014

2014
[19]

Improved algorithms for decremental single-source reachability on directed gr aphs

Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Improved algorithms for decremental single-source reachability on directed gr aphs. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, K yoto, Japan, July 6-10, 2015, Proceedings, ...

2015
[20]

Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and de randomization

Monika Henzinger, Sebastian Krinninger, and Danupon N anongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and de randomization. SIAM J. Comput. , 45(3):947–1006, 2016

2016
[21]

Seybold, and Ch ristopher Y e

Monika Henzinger, Barna Saha, Martin P . Seybold, and Ch ristopher Y e. On the complexity of algorithms with predictions for dynamic graph problems. In V enkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, I TCS 2024, January 30 to February...

2024
[22]

Fully dynamic biconnectivity and transitive closure

Monika Rauch Henzinger and V alerie King. Fully dynamic biconnectivity and transitive closure. In Proceedings of IEEE 36th Annual F oundations of Computer Science, pages 664–672. IEEE, 1995

1995
[23]

Learning-based frequency estimation algorithms

Chen-Y u Hsu, Piotr Indyk, Dina Katabi, and Ali V akilian . Learning-based frequency estimation algorithms. In Proc. 7th Annual International Conference on Learning Repr esentations (ICLR) , 2019

2019
[24]

Online page migration with ML advice

Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitro vic, and Ronitt Rubinfeld. Online page migration with ML advice. In Gustau Camps-V alls, Francisco J. R. Ruiz, and Isabel V alera, editors, International Conference on Artiﬁcial Intelligence and St atistics, (AISTATS), volum...

2022
[25]

Onlin e algorithms for weighted paging with predictions

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Onlin e algorithms for weighted paging with predictions. In Artur Czumaj, Anuj Dawar, and Emanuela Mere lli, editors, 47th International Colloquium on Automata, Languages, and Programming, (ICAL P), volume 168 of LIPIcs, pages 6...

2020
[26]

Chi, Jeffrey Dean, and Neo klis Polyzotis

Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neo klis Polyzotis. The case for learned index structures. In Gautam Das, Christopher M. Jermaine, a nd Philip A. Bernstein, editors, Proc. 44th Annual International Conference on Management o f Data, (SIGMOD) , pages 489–5...

2018
[27]

Incremental sssp for sparse digraphs beyond the hopset barrier

Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gu tenberg. Incremental sssp for sparse digraphs beyond the hopset barrier. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3452–3481. SIAM, 2022

2022
[28]

Speeding up bellman ford via minimum vi- olation permutations

Silvio Lattanzi, Ola Svensson, and Sergei V assilvitskii. Speeding up bellman ford via minimum vi- olation permutations. In Andreas Krause, Emma Brunskill, K yunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Lea...

2023
[29]

Learning aug mented binary search trees

Honghao Lin, Tian Luo, and David Woodruff. Learning aug mented binary search trees. In Proc. 35th International Conference on Machine Learning (ICML) , pages 13431–13440. PMLR, 2022. 19

2022
[30]

Woodruff

Honghao Lin, Tian Luo, and David P . Woodruff. Learning a ugmented binary search trees. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepe sv´ ari, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 1 7-23 July 2022, Baltim...

2022
[31]

Liu and V aidehi Srinivas

Quanquan C. Liu and V aidehi Srinivas. The predicted-up dates dynamic model: Ofﬂine, incremen- tal, and decremental to fully dynamic transformations. In S hipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theor y, volume 247 of Proceed...

2024
[32]

Competit ive caching with machine learned advice

Thodoris Lykouris and Sergei V assilvitskii. Competit ive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021

2021
[33]

Faster approximation schemes for fr actional multicommodity ﬂow problems via dynamic graph algorithms

Aleksander Madry. Faster approximation schemes for fr actional multicommodity ﬂow problems via dynamic graph algorithms. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 121–130, 2010

2010
[34]

Online list labeling with predictions

Samuel McCauley, Benjamin Moseley, Aidin Niaparast, a nd Shikha Singh. Online list labeling with predictions. In A. Oh, T. Naumann, A. Globerson, K. Saen ko, M. Hardt, and S. Levine, editors, Proc. 36th Conference on Neural Information Processing Sys tems (NeurIPS), volume 36,...

2023
[35]

Incremental topological ordering and cycle detection with predictions

Samuel Mccauley, Benjamin Moseley, Aidin Niaparast, a nd Shikha Singh. Incremental topological ordering and cycle detection with predictions. In Ruslan Sa lakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, an d Felix Berkenkamp, editors...

2024
[36]

A model for learned bloom ﬁlters and optimizing by sandwiching

Michael Mitzenmacher. A model for learned bloom ﬁlters and optimizing by sandwiching. Proc. 31st Conference on Neural Information Processing Systems ( NeurIPS), 31, 2018

2018
[37]

Fully-dynamic-to- incremental reductions with known deletion order (e.g

Binghui Peng and Aviad Rubinstein. Fully-dynamic-to- incremental reductions with known deletion order (e.g. sliding window). In Telikepalli Kavit ha and Kurt Mehlhorn, editors, 2023 Symposium on Simplicity in Algorithms, SOSA 2023, Florence , Italy, January 23-25, 2023 , pages...

2023
[38]

Learning-augmented maximum ﬂow

Adam Polak and Maksym Zub. Learning-augmented maximum ﬂow. Information Processing Letters, 186:106487, 2024

2024
[39]

New algorithms and hardness for incremental single-source shortest paths in directed graphs

Maximilian Probst Gutenberg, Virginia V assilevska Wi lliams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 153–166, 2020

2020
[40]

On dynamic shortest paths pr oblems

Liam Roditty and Uri Zwick. On dynamic shortest paths pr oblems. Algorithmica, 61(2):389–401, 2011

2011
[41]

Discrete-convex-anal ysis-based framework for warm-starting algorithms with predictions

Shinsaku Sakaue and Taihei Oki. Discrete-convex-anal ysis-based framework for warm-starting algorithms with predictions. In 35th Conference on Neural Information Processing Systems (NeurIPS), 2022

2022
[42]

An on-line edge-deleti on problem

Y ossi Shiloach and Shimon Even. An on-line edge-deleti on problem. Journal of the ACM (JACM), 28(1):1–4, 1981

1981
[43]

warm start

V aidehi Srinivas and Avrim Blum. Competitive strategi es to use “warm start” algorithms with predictions. In Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algo rithms, SODA

2025
[44]

Partitioned learned bloom ﬁlters

Kapil V aidya, Eric Knorr, Michael Mitzenmacher, and Ti m Kraska. Partitioned learned bloom ﬁlters. In Proc. 9th Annual International Conference on Learning Repr esentations (ICLR), 2021

2021
[45]

On dynamic graph algorithms with predictions

Jan van den Brand, Sebastian Forster, Y asamin Nazari, a nd Adam Polak. On dynamic graph algorithms with predictions. In David P . Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 35...

2024
[46]

Robust learning-augmented dictionaries

Ali Zeynali, Shahin Kamali, and Mohammad Hajiesmaili. Robust learning-augmented dictionaries. In F orty-ﬁrst International Conference on Machine Learning , 2024

2024
[47]

Robust learning-augmented dictionaries

Ali Zeynali, Shahin Kamali, and Mohammad Hajiesmaili. Robust learning-augmented dictionaries. In F orty-ﬁrst International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. 21

2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Sorting with predic tions

Xingjian Bai and Christian Coester. Sorting with predic tions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

work page 2023

[2] [2]

Learning-augment ed priority queues

Ziyad Benomar and Christian Coester. Learning-augment ed priority queues. In The Thirty-eighth Annual Conference on Neural Information Processing System s, 2024

work page 2024

[3] [3]

Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh

Ioana O. Bercea, Jakob Bæk Tejs Houen, and Rasmus Pagh. Da isy Bloom Filters. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm The ory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs ), pages 9:1–9:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentr um f¨ ur Informatik

work page 2024

[4] [4]

Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time

Aaron Bernstein. Fully dynamic (2+ ε) approximate all-pairs shortest paths with fast query and close to linear update time. In 2009 50th Annual IEEE Symposium on F oundations of Computer Science, pages 693–702. IEEE, 2009

work page 2009

[5] [5]

Maintaining shortest paths under dele tions in weighted directed graphs

Aaron Bernstein. Maintaining shortest paths under dele tions in weighted directed graphs. SIAM Journal on Computing, 45(2):548–574, 2016. 17

work page 2016

[6] [6]

Deterministic decremental SSSP and approximate min-cost ﬂow in almost-li near time

Aaron Bernstein, Maximilian Probst Gutenberg, and That chaphol Saranurak. Deterministic decremental SSSP and approximate min-cost ﬂow in almost-li near time. In 62nd IEEE Annual Symposium on F oundations of Computer Science, FOCS 2021, De nver , CO, USA, February 7-10, 2022, pages 1000–1008. IEEE, 2021

work page 2021

[7] [7]

Near-optimal decre- mental SSSP in dense weighted digraphs

Aaron Bernstein, Maximilian Probst Gutenberg, and Chri stian Wulff-Nilsen. Near-optimal decre- mental SSSP in dense weighted digraphs. In Sandy Irani, edit or, 61st IEEE Annual Symposium on F oundations of Computer Science, FOCS 2020, Durham, NC, USA , November 16-19, 2020 , pages 1112–1122. IEEE, 2020

work page 2020

[8] [8]

Adaptive probing policies for shortest path routing

Aditya Bhaskara, Sreenivas Gollapudi, Kostas Kollias, and Kamesh Munagala. Adaptive probing policies for shortest path routing. Advances in Neural Information Processing Systems (NeurIP S), 33:8682–8692, 2020

work page 2020