論文の概要: 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%を上回っている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。