Incremental Approximate Single-Source Shortest Paths with Predictions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912230372540416 |
|---|---|
| author | McCauley, Samuel Moseley, Benjamin Niaparast, Aidin Niaparast, Helia Singh, Shikha |
| author_facet | McCauley, Samuel Moseley, Benjamin Niaparast, Aidin Niaparast, Helia Singh, Shikha |
| contents | 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 $σ$ 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σ$ which is used to ``warm start'' its state.
As our main result, we design a learned algorithm that maintains $(1+ε)$-approximate single-source shortest paths, which runs in $\tilde{O}(m η\log W/ε)$ time, where $W$ is the weight of the heaviest edge and $η$ 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 $σ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08125 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Incremental Approximate Single-Source Shortest Paths with Predictions McCauley, Samuel Moseley, Benjamin Niaparast, Aidin Niaparast, Helia Singh, Shikha Data Structures and Algorithms Machine Learning 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 $σ$ 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σ$ which is used to ``warm start'' its state. As our main result, we design a learned algorithm that maintains $(1+ε)$-approximate single-source shortest paths, which runs in $\tilde{O}(m η\log W/ε)$ time, where $W$ is the weight of the heaviest edge and $η$ 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 $σ$ 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. |
| title | Incremental Approximate Single-Source Shortest Paths with Predictions |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2502.08125 |