論文の概要: The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning

• arxiv url: http://arxiv.org/abs/2610.28994v1
• Date: Tue, 20 Oct 2026 23:48:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.162056
• Title: The Optimal Sampler for Diverse TSP Solutions: Characterization, Limits, and Learning
• Title（参考訳）: 多様なTSPソリューションのための最適サンプリング: 評価, 限界, 学習
• Abstract要約: D-TSPをサンプリングステージと選択ステージに分解する新しいフレームワークを提案する。 木々をサンプルにしてツアーに変換するパイプラインは,原則としてプールの品質を損なうものではないことを実証する。
• 参考スコア（独自算出の注目度）: 0.26999000177990923
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address the Diverse Traveling Salesman Problem (D-TSP) that seeks a set of $k$ distinct TSP tours. Each selected tour must not exceed a prescribed multiple of the optimal tour length, while the maximum pairwise Jaccard similarity within the selected set is minimized. This formulation is important for applications requiring both solution quality and fault tolerance, such as logistics planning, robotics, and strategic patrolling. We propose a novel hybrid framework that decomposes D-TSP into a sampling stage and a selection stage. The selection stage is a max-min dispersion problem, for which any approximation better than a factor of two is NP-hard; we therefore focus on the sampling stage. Our contributions are both theoretical and empirical. Theoretically, we give two end-to-end guarantees for the optimal sampling distribution, from two perspectives: including an optimal set in the sampled pool, or having at least $k$ mutually distant tours in the pool. The second reduces the number of samples from exponential to linear in $k$, at the cost of weakening the benchmark from the best $k$ tours to the best $βk$ for some $β> 1$. For practical use, we prove that a pipeline that samples spanning trees and then converts to tours does not hurt the quality of the pool in principle. Empirically, both objectives are learnable, and our experiments not only validate the analysis but also outperform the baselines on both in-distribution and out-of-distribution instances, by a single trained model with no fine-tuning.
• Abstract（参考訳）: 海外旅行セールスマン問題 (D-TSP) に対処し, 異なるTSPツアーのセットとして$kを求める。 選択されたツアーは、最適なツアー長の所定回数を超えるべきではないが、選択されたセット内の最大対角ジャカード類似性が最小化されている。 この定式化は、ロジスティクス計画、ロボット工学、戦略的パトロールなど、ソリューションの品質と耐障害性の両方を必要とするアプリケーションにとって重要である。 D-TSPをサンプリングステージと選択ステージに分解する新しいハイブリッドフレームワークを提案する。 選択段階は最大ミン分散問題であり、2の係数よりも良い近似はNPハードであり、サンプリング段階に焦点をあてる。 私たちの貢献は理論的かつ実証的です。 理論的には、サンプルプールの最適セットを含む2つの視点から、最適なサンプリング分布を2つのエンドツーエンドで保証する。 2つ目は、ベンチマークを最高の$k$ツアーから、ある$β> 1$の$βk$まで弱めるために、指数関数的なサンプル数を$k$で線形にする。 実際に使用するために、木々をサンプルにしてツアーに変換するパイプラインが、原則としてプールの品質を損なうことはないことを証明した。 実験では,2つの目的が学習可能であり,分析結果の検証だけでなく,微調整のない単一学習モデルにより,分布内および分布外の両方のベースラインを上回ります。

関連論文リスト

• Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts [57.07359479446759]
  Mixture-of-Experts (MoE)モデルは、入力依存のルーティング機構を通じて専門の専門家を結合する。 専門家とゲーティングネットワークの両方がリプシッツである場合、最小二乗MoE推定器の推定誤差について検討する。
  論文  参考訳（メタデータ） (2026-10-10T16:24:04Z)
• Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion [0.26999000177990923]
  ディバース・トラベリング・セールスマン問題(Diverse Traveling Salesman Problem, D-TSP)は、異なるツアーのセットを求める双基準最適化問題である。 D-TSPを2つの効率的なステップに分解する新しいハイブリッドフレームワークを提案する。 当社のアプローチは,大規模インスタンス(783都市)の360倍以上高速です。
  論文  参考訳（メタデータ） (2026-01-03T09:37:18Z)
• BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling [16.38043428743923]
  本稿では,大言語モデルからのサンプルを,ベスト・オブ・nドルサンプリングを用いてヒトの嗜好に合わせることの問題点について述べる。 基本モデルからKL距離に対する勝利率とのトレードオフの観点から,n$の最高値が本質的に最適であることを示す。 実験により,BoNBoNアライメントは基本方針に好適なモデルの生成において,大幅な改善をもたらすことが示された。
  論文  参考訳（メタデータ） (2024-06-02T18:42:57Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)

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

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