論文の概要: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP

• arxiv url: http://arxiv.org/abs/2302.06582v3
• Date: Thu, 27 Jun 2024 09:09:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 20:35:54.774755
• Title: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
• Title（参考訳）: 非ユークリッド型TSPに対するコンベックス・ハル・チープ・インサーション・ヒューリスティック
• Authors: Mithun Goutham, Meghna Menon, Sarah Garrow, Stephanie Stockar,
• Abstract要約: 凸船体で最も安価な挿入は、ユークリッド空間におけるトラベリングセールスパーソン問題に対する良い解を生み出すことが知られている。 提案手法は多次元スケーリングを用いて、まず点をユークリッド空間に投影することにより、アルゴリズムを初期化する凸殻の生成を可能にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The convex hull cheapest insertion heuristic is known to produce good solutions to the Traveling Salesperson Problem in Euclidean spaces, but it has not been extended to the non-Euclidean case. The proposed adaptation uses multidimensional scaling to first project the points into a Euclidean space, thereby enabling the generation of the convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding impassable separators to the TSPLIB benchmark data-set, or by using the L1 norm as a metric. This adapted heuristic is demonstrated to outperform the commonly used Nearest Neighbor heuristic and Nearest Insertion heuristic in 89% and 99% of the cases studied, respectively. When the genetic algorithm and ant colony optimization algorithms are provided 1 minute of computation time, the proposed heuristic tour costs are lower than the mean metaheuristic solutions found in 87% and 95% of the instances, respectively.
• Abstract（参考訳）: 凸船体で最も安価な挿入ヒューリスティックは、ユークリッド空間におけるトラベリングセールスパーソン問題に対する優れた解を生み出すことが知られているが、非ユークリッドの場合まで拡張されていない。 提案手法は多次元スケーリングを用いて、まず点をユークリッド空間に投影することにより、アルゴリズムを初期化する凸殻の生成を可能にする。 提案アルゴリズムを評価するために、TSPLIBベンチマークデータセットに非許容セパレータを追加するか、L1ノルムをメトリックとして使用することにより、非ユークリッド空間を生成する。 この適応型ヒューリスティックは, 89%, 99%の症例において, 一般的に使用されているNearest Neighbor HeuristicおよびNearest Insertion Heuristicよりも優れていた。 遺伝的アルゴリズムとアリコロニー最適化アルゴリズムが1分間の計算時間で提供される場合、提案したヒューリスティックツアーコストは、各インスタンスの87%と95%のメタヒューリスティックソリューションよりも低い。

関連論文リスト

• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  ユークリッド距離情報点対を埋め込む適切な点を見つける問題は、コアタスクとサブマシン学習の問題の両方として生じる。 本稿では,最小限のサンプル数を考えると,この問題を解決することを目的とする。
  論文  参考訳（メタデータ） (2024-10-22T13:02:12Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler [23.166642097170545]
  我々は、密度の対数ラプラス変換(LLT)と呼ばれる物体によって自然に正則化を誘導する、最近の[LST21]の近位サンプルの非ユークリッドアナログを開発する。 本稿では,Euclidean 設定 [GLL22] に適合させるため,$ell_p$ と $p in [1, 2]$ のSchatten-$p$ノルムの差分プライベート凸最適化の値オラクル複雑性を改善するとともに,最先端の余剰リスク境界を維持した。
  論文  参考訳（メタデータ） (2023-02-13T04:08:41Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension [12.354076490479514]
  本稿では,DPCP (Dual principal Component Pursuit) が未知の部分空間次元の問題を確実に解決できることを示す。 プロジェクテッド・サブ段階降下法(PSGM)の複数インスタンスの実行に基づく,非常に単純なアルゴリズムを提案する。 特に、1)すべての問題インスタンスが部分空間のヌル空間のベクトルに収束し、2)問題インスタンスの解のアンサンブルが、部分空間のヌル空間に完全にまたがるほど十分に多様であることを示す。
  論文  参考訳（メタデータ） (2022-01-22T15:36:03Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。 このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
  論文  参考訳（メタデータ） (2021-03-08T13:18:45Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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