論文の概要: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
- arxiv url: http://arxiv.org/abs/2302.06582v2
- Date: Sat, 27 Jan 2024 19:29:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-31 00:56:36.787458
- Title: A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP
- Title(参考訳): 非ユークリッド tsp に対する最も安価な凸殻挿入ヒューリスティック
- Authors: Mithun Goutham, Meghna Menon, Sarah Garrow and Stephanie Stockar
- Abstract要約: 凸船体で最も安価な挿入は、ユークリッド空間におけるトラベリングセールスパーソン問題に対する良い解を生み出すことが知られている。
提案手法は多次元スケーリングを用いてユークリッド空間内のこれらの点を近似する。
このアルゴリズムは、調査されたケースの96%において、一般的に使われているNearest Neighborアルゴリズムより優れていることを示した。
- 参考スコア(独自算出の注目度): 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 Traveling Salesperson Problem in Euclidean spaces, but it has
not been extended to the non-Euclidean case. To address the difficulty of
dealing with obstacles in the non-Euclidean space, the proposed adaptation uses
multidimensional scaling to first approximate these points in a Euclidean
space, thereby enabling the generation of the convex hull that initializes the
algorithm. To evaluate the proposed algorithm, the TSPLIB benchmark data-set is
modified by adding impassable separators that produce non-Euclidean spaces. The
algorithm is demonstrated to outperform the commonly used Nearest Neighbor
algorithm in 96% of the cases studied.
- Abstract(参考訳): 凸船体で最も安価な挿入ヒューリスティックは、ユークリッド空間におけるトラベリングセールスパーソン問題に対する優れた解を生成することが知られているが、非ユークリッドの場合まで拡張されていない。
非ユークリッド空間の障害物に対処することの難しさを解決するため、提案手法は多次元スケーリングを用いてユークリッド空間のこれらの点をまず近似し、アルゴリズムを初期化する凸殻の生成を可能にする。
提案アルゴリズムを評価するために,非ユークリッド空間を生成する非許容セパレータを追加することにより,TSPLIBベンチマークデータセットを改良する。
このアルゴリズムは、調査されたケースの96%において、一般的に使われているNearest Neighborアルゴリズムより優れていることを示した。
関連論文リスト
- Robust Kernel Sparse Subspace Clustering [0.0]
本稿では,カーネルスパースSC (RKSSC) アルゴリズムを初めて提案する。
この概念は、原則として他のSCアルゴリズムにも適用でき、この種の汚職の存在に対して堅牢性を達成することができる。
論文 参考訳(メタデータ) (2024-01-30T14:12:39Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳(メタデータ) (2023-06-04T17:52:49Z) - 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 [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳(メタデータ) (2022-06-04T18:53:44Z) - Linear Convergence of the Subspace Constrained Mean Shift Algorithm:
From Euclidean to Directional Data [3.60425753550939]
SCMSアルゴリズムは、適応的なステップサイズを持つ部分空間制約付き勾配上昇アルゴリズムの特別な変種であると主張する。
提案した方向性SCMSアルゴリズムの線形収束性を証明する。
論文 参考訳(メタデータ) (2021-04-29T01:46:35Z) - Low-Rank Sinkhorn Factorization [45.87981728307819]
本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。
このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
論文 参考訳(メタデータ) (2021-03-08T13:18:45Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。