論文の概要: Tightest Admissible Shortest Path

• arxiv url: http://arxiv.org/abs/2308.08453v2
• Date: Wed, 27 Mar 2024 21:46:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-29 21:53:04.703737
• Title: Tightest Admissible Shortest Path
• Title（参考訳）: 最短経路
• Authors: Eyal Weiss, Ariel Felner, Gal A. Kaminka,
• Abstract要約: グラフにおける最短経路問題はAIの基本である。 本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。 我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.928034044959278
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.
• Abstract（参考訳）: グラフにおける最短経路問題は、AIの基本である。 問題のほとんどすべての変種とそれを解決する関連するアルゴリズムは、エッジウェイト計算時間と、その重みの不確実性との共通関係を無視している。 これは、これらの要因を考慮に入れれば、関連するアプリケーションのパフォーマンスが向上する可能性があることを意味します。 近年,重み付き有向グラフの一般化フレームワークが提案され,エッジウェイトを複数回(推定)し,精度の向上と実行時費用の増大を図った。 我々は,最短最短経路 (TASP) を最適コストに縛られた最短経路 (TASP) を求める問題を提起するために,この枠組みを構築した。 これは、エッジウェイト不確実性を計算コストで交換できる境界不確実性への最短経路問題の一般化である。 我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。 経験的評価はこのアプローチの有効性を支持する。

関連論文リスト

• Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
  より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。 我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
  論文  参考訳（メタデータ） (2024-05-08T09:25:39Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates [13.046825574678579]
  グラフにおける最短経路問題は、AI理論と応用の基礎である。 本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。 次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
  論文  参考訳（メタデータ） (2022-08-22T22:07:27Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。 同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
  論文  参考訳（メタデータ） (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)
• Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
  ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。 このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
  論文  参考訳（メタデータ） (2020-02-20T12:04:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。