論文の概要: TSP with Predictions: Heatmap to Tour with Provable Guarantees

• arxiv url: http://arxiv.org/abs/2607.03791v1
• Date: Sat, 04 Jul 2026 09:43:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:29.722034
• Title: TSP with Predictions: Heatmap to Tour with Provable Guarantees
• Title（参考訳）: 予報付きTSP:ハザードマップの案内付きツアーへ
• Abstract要約: 一般的なアプローチは、ニューラルネットワークをトレーニングして、各エッジが最適なツアーの一部である可能性を推定するヒートマップを出力することである。 得られた熱マップの品質と近似比を関連付ける理論的保証付きツアーに熱マップを変換するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.2207014199488277
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent efforts to apply ML to algorithmic problems, TSP has also become a natural testbed for the development of ML-based techniques. A common approach is to train a neural network to output a heatmap estimating the likelihood of each edge to be part of the optimal tour; however, converting such a heatmap into an actual tour remains a non-trivial and often computationally intensive step. In this work, we propose algorithms for transforming heatmaps into tours with theoretical guarantees linking the achieved approximation ratio to the quality of the provided heatmap. In the spirit of algorithms with predictions, our results can be described as $(1+2\fracη{\mathrm{OPT}})$-approximation algorithms, where $η$ denotes the L1 distance between the prediction (heatmap) and an optimal solution (tour). Since the previous works lack such explicit guarantees, we compare our approach against them experimentally.
• Abstract（参考訳）: トラベリングセールスパーソン問題(TSP)は、アルゴリズムの古典的理論における最適化手法の強みを評価するベンチマークとして長年使われてきた。 近年のアルゴリズム問題へのMLの適用において、TSPはMLベースの技術開発のための自然なテストベッドとなっている。 一般的なアプローチは、ニューラルネットワークをトレーニングして、最適なツアーの一部として各エッジの確率を推定するヒートマップを出力することであるが、そのようなヒートマップを実際のツアーに変換することは、非自明でしばしば計算集約的なステップである。 本研究では,得られた熱マップと得られた熱マップの品質の近似比を関連付ける理論的保証付きツアーに熱マップを変換するアルゴリズムを提案する。 予測を伴うアルゴリズムの精神では、我々の結果は$(1+2\fracη{\mathrm{OPT}})$-approximationアルゴリズムと表現でき、$η$は予測(熱マップ)と最適解(Tour)の間のL1距離を表す。 これまでの研究はそのような明確な保証を欠いているため、我々のアプローチを実験的に比較する。

関連論文リスト

• When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection [0.15469452301122175]
  オンラインセレクション(OAS)は、フィットネスのランドスケープの変化に最適化プロセスを適用することを目的としており、特定のポートフォリオから任意のアルゴリズムを上回ることが期待されている。 現在、OASがスピードアップを達成できるという理論的な結果は得られていない。 本稿では,2つのアルゴリズムの切り換えが,それぞれのアルゴリズムの分離よりも問題的に高速であることを示す最初の理論的例を示す。
  論文  参考訳（メタデータ） (2026-04-08T18:11:36Z)
• Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport [0.0]
  複数のターゲットトラッキングでは、異なるトラッキングアルゴリズムの性能を評価することが重要である。 軌道一般化最適部分パターン割当量(TGOSPA)は,最近提案された評価基準である。 本稿では,TGOSPA問題を不均衡なマルチマルジナル最適輸送問題としてキャストすることで,TGOSPAメトリックを評価する近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-12T14:51:03Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。 そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。 我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
  論文  参考訳（メタデータ） (2023-01-23T19:13:25Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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