論文の概要: Incremental Approximate Single-Source Shortest Paths with Predictions
- arxiv url: http://arxiv.org/abs/2502.08125v1
- Date: Wed, 12 Feb 2025 05:06:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 13:44:49.827900
- Title: Incremental Approximate Single-Source Shortest Paths with Predictions
- Title（参考訳）: 予測付きインクリメンタル・アロキシマト・ソース・ショート・パス
- Authors: Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, Shikha Singh,
- Abstract要約: インクリメンタルグラフにおける最短経路を近似的に維持する基本データ構造問題について検討する。
これらのテクニックは、直ちに全ペアの最短パス設定にも拡張されます。
私たちのアルゴリズムは、予測がほぼ完璧である場合(オフラインアルゴリズムとほぼ同等の速さで実行される)一貫性があります。
- 参考スコア（独自算出の注目度）: 10.749658550545238
- License:
- 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.
- Abstract（参考訳）: アルゴリズム・ウィズ・予測フレームワークは、ワースト・ケースを越えた競合率を改善したオンライン・アルゴリズムの開発に広く利用されている。
近年,データ構造設計における予測の活用への関心が高まっている。
本稿では,アルゴリズムと予測モデルを用いたインクリメンタルグラフにおいて,最短経路を近似的に維持する基本データ構造問題について検討する。
一度に挿入されるエッジのシーケンス$\sigma$が与えられた場合、ゴールは、各時間ステップにおいて、ソースからグラフの各頂点への最も短いパスを近似的に維持することである。
エッジが到着する前に、データ構造はオンラインエッジシーケンス$\hat{\sigma}$の予測が与えられます。
その結果,1+\epsilon)$-approximate single-source shortest paths は $\tilde{O}(m \eta \log W/\epsilon)$ time で実行される。
これらのテクニックは、直ちに全ペアの最短パス設定にも拡張されます。
我々のアルゴリズムは、予測がほぼ完全であるときに一貫性(オフラインアルゴリズムとほぼ同等の性能)を持ち、予測誤差に対する性能のスムーズな劣化があり、最悪の場合、最適なオフラインアルゴリズムと対数係数を一致させる。
ビルディングブロックとして、オフラインのインクリメンタルなインクリメンタルなシングルソース・ショート・パス問題について検討する。
この問題において、エッジシーケンス $\sigma$ は先験であることが知られており、その目標は、すべての $t$ に対して、最初の $t$ エッジからなる中間グラフ $G_t$ の最短パスの長さを効率よく返すことである。
オフラインインクリメンタル問題は(予測なしで)最悪のケース設定で定義され、独立した関心を持つことに注意してください。
関連論文リスト
- The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
我々は,非プライベートなストリーミングおよび静的グラフアルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。
完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
論文 参考訳（メタデータ） (2024-07-24T20:15:07Z) - Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文 参考訳（メタデータ） (2024-05-06T17:38:20Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳（メタデータ） (2022-08-22T22:07:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Quantum Algorithm for the Longest Trail Problem [0.0]
最長経路問題に対する量子アルゴリズムを提案する。
アルゴリズムの実行時間は$O* (1.728m)$である。
論文 参考訳（メタデータ） (2021-12-27T09:42:19Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Regret Bounds for Stochastic Shortest Path Problems with Linear Function
Approximation [29.549633678730054]
線形関数近似を用いたエピソディック最短経路問題に対する2つのアルゴリズムを提案する。
1つは計算コストが高いが、$tildeo (sqrtb_star3 d3 k/cmin )$ regret が得られる。
2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。
論文 参考訳（メタデータ） (2021-05-04T16:05:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。