論文の概要: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean and Precedence Constrained TSPs

• arxiv url: http://arxiv.org/abs/2302.06582v1
• Date: Sun, 5 Feb 2023 13:56:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-19 14:22:04.673341
• Title: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean and Precedence Constrained TSPs
• Title（参考訳）: 非ユークリッドおよび順列制約付きTSPのための凸ハルチープ挿入ヒューリスティック
• Authors: Mithun Goutham, Meghna Menon, Sarah Garrow and Stephanie Stockar
• Abstract要約: 本稿では、この問題を非ユークリッド版に適応させ、優先制約付き問題にさらに拡張する。 提案アルゴリズムは, 優先制約のない場合の97%において, 一般的に使用されている近縁アルゴリズムより優れていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The convex hull cheapest insertion heuristic is known to generate good solutions to the Euclidean Traveling Salesperson Problem. This paper presents an adaptation of this heuristic to the non-Euclidean version of the problem and further extends it to the problem with precedence constraints, also known as the Sequential Ordering Problem. To test the proposed algorithm, the well-known TSPLIB benchmark data-set is modified in a replicable manner to create non-Euclidean instances and precedence constraints. The proposed algorithm is shown to outperform the commonly used Nearest Neighbor algorithm in 97% of the cases that do not have precedence constraints. When precedence constraints exist such that the child nodes are centrally located, the algorithm again outperforms the Nearest Neighbor algorithm in 98% of the studied instances. Considering all spatial layouts of precedence constraints, the algorithm outperforms the Nearest Neighbor heuristic 68% of the time.
• Abstract（参考訳）: 凸船体で最も安価な挿入ヒューリスティックは、ユークリッド旅行販売問題に対する優れた解決策を生み出すことが知られている。 本稿では,このヒューリスティックを非ユークリッド版の問題に適用し,逐次順序問題としても知られる先行制約問題にまで拡張する。 提案アルゴリズムをテストするために、よく知られたTSPLIBベンチマークデータセットを複製可能な方法で修正し、非ユークリッドインスタンスと優先制約を生成する。 提案アルゴリズムは, 優先制約のない場合の97%において, 一般的に使用されている近縁アルゴリズムより優れていることを示す。 子ノードが中心に位置するような優先制約が存在する場合、このアルゴリズムは、研究されたインスタンスの98%で、最も近い隣接アルゴリズムを上回る。 優先制約の全ての空間的レイアウトを考えると、アルゴリズムは最寄りのヒューリスティックな68%を上回っている。

関連論文リスト

• 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)

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

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