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

• arxiv url: http://arxiv.org/abs/2302.06582v4
• Date: Mon, 1 Jul 2024 15:56:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-02 18:29:26.326188
• 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 never been extended to the non-Euclidean problem. This paper proposes an adaptation that uses multidimensional scaling to first project the points from a non-Euclidean space into a Euclidean equivalent space, thereby enabling the generation of a convex hull that initializes the algorithm. To evaluate the proposed algorithm, non-Euclidean spaces are created by adding separators to the Euclidean 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 88% and 99% of the cases studied, respectively. When compared with metaheuristic algorithms, the proposed heuristic's tour costs are lower than the solutions found by the genetic algorithm and ant colony optimization algorithm in 87% and 95% of the instances, respectively.
• Abstract（参考訳）: 凸船体で最も安価な挿入ヒューリスティックは、ユークリッド空間におけるトラベリングセールスパーソン問題に対する優れた解を生み出すことが知られているが、非ユークリッド問題に拡張されることは一度もない。 本稿では,多次元スケーリングを用いて,まず非ユークリッド空間からユークリッド同値空間へ点を投影し,アルゴリズムを初期化する凸殻の生成を可能にする適応法を提案する。 提案アルゴリズムを評価するために、ユークリッドのTSPLIBベンチマークデータセットにセパレータを追加するか、L1ノルムを計量として用いることで、非ユークリッド空間を生成する。 この適応型ヒューリスティックは,88%,99%の症例において,一般的に使用されている近縁型ヒューリスティックと近縁型インサーションヒューリスティックより優れていた。 メタヒューリスティックアルゴリズムと比較すると、提案したヒューリスティックのツアーコストは、遺伝的アルゴリズムとアリコロニー最適化アルゴリズムの解より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)

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

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