論文の概要: GES-TSP: Graph Edge Sparsification for TSP

• arxiv url: http://arxiv.org/abs/2607.09708v1
• Date: Tue, 23 Jun 2026 11:13:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-19 21:54:20.380306
• Title: GES-TSP: Graph Edge Sparsification for TSP
• Title（参考訳）: GES-TSP: TSPのためのグラフエッジスカラー化
• Authors: Tianfeng Chen, Xianyue Li,
• Abstract要約: Graph Edge Sparsification (GES) はユークリッド旅行セールスマン問題(TSP)の学習に基づくスペーシフィケーション手法である 提案手法は,異なるインスタンスに対するスペーシフィケーショングラフを適応的に生成し,グラフサイズを大幅に削減し,解法を高速化する。 実験の結果,提案手法はMATILDAデータセット上で最大95%のエッジを創出し,解のギャップを最適値の1%に抑えることができた。
• 参考スコア（独自算出の注目度）: 0.8670873561640903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean TSP. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process. Experimental results demonstrate that our sparsification method can prune up to 95% of edges on the MATILDA dataset, while keeping the solution gap within 1% of the optimal value. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark.In some large-scale instances, the pruning rate exceeds 99%, while the optimality gap remains below 1%.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)の大規模インスタンスの解決には計算コストがかかる。 研究者はしばしば計算効率を改善するためにグラフスペーシフィケーション法を用いる。 従来のスパーシフィケーション手法は一般に固定ヒューリスティックに依存しており、インスタンス固有の構造情報を完全に活用できない。 本稿では,Euclidean TSPの学習に基づくスカラー化手法であるGraph Edge Sparsification (GES)を提案する。 幾何構造情報と組合せ最適化技術を組み合わせることにより,提案手法は異なるインスタンスに対してスペーシフィケーショングラフを適応的に生成し,グラフサイズを大幅に削減し,解法を高速化する。 実験の結果,提案手法はMATILDAデータセット上で最大95%のエッジを創出し,解のギャップを最適値の1%に抑えることができた。 さらに,TSPLIBベンチマークでは,プルーニング率が99%を超え,最適性ギャップが1%以下である場合も少なくない。

関連論文リスト

• AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network [50.69521065962045]
  Anisotropic Graph Diffusion Network (AGDN) はトラベリングセールスマン問題(TSP)を解決するために設計された新しいグラフニューラルネットワークフレームワークである。 提案手法は,1) 完全連結TSPグラフにおける情報的トポロジ的事前の欠如,2) グラフスペーシフィケーション手法により最適解における接続ノードの喪失,の2つの問題に対処する。 AGDNは、競争力を維持しながら、既存の手法を一貫して上回る。
  論文  参考訳（メタデータ） (2026-06-17T15:24:37Z)
• Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines [4.381143313862113]
  グラフスペーサー化(Graph Sparsification)は、エッジを縮小してスペーサー地区を生成するテクニックである。 GNNのトレーニングとスペーサー付きグラフの推論に関する最初の総合的研究を行う。 以上の結果から,K-Neighborスペーサーは製品グラフ上のモデルサービス性能を0.7%の精度で11.7倍改善することがわかった。
  論文  参考訳（メタデータ） (2026-03-07T00:02:33Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  グラフ拡散型ソリューション生成(GDSG)法を提案する。 このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。 グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
  論文  参考訳（メタデータ） (2024-12-11T11:13:43Z)
• Unifews: You Need Fewer Operations for Efficient Graph Neural Networks [9.66321358222326]
  グラフニューラルネットワーク(GNN)は、有望な性能を示すが、グラフスケールの行列に対するリソース集約的な操作のコストがかかる。 グラフと重み行列の演算を統一し、GNN学習効率を向上させるための連成スカラー化手法であるUnifewsを提案する。
  論文  参考訳（メタデータ） (2024-03-20T03:07:30Z)
• Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization [14.23697277904244]
  Reweighted Gradient Descent (RGD) は、動的サンプル再重み付けによりディープニューラルネットワークの性能を向上させる新しい最適化手法である。 本稿では,教師付き学習,メタラーニング,ドメイン外一般化など,様々な学習課題におけるRGDの有効性を示す。
  論文  参考訳（メタデータ） (2023-06-15T15:58:04Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
  グラフ計算のための特徴指向最適化を備えたスケーラブルグラフニューラルネットワーク(GNN)であるSCARAを提案する。 SCARAはノードの特徴からグラフの埋め込みを効率的に計算し、機能の結果を選択して再利用することでオーバーヘッドを減らします。 利用可能な最大10億のGNNデータセットであるPapers100M(1110万ノード、1.6Bエッジ)を100秒でプリ計算するのが効率的である。
  論文  参考訳（メタデータ） (2022-07-19T10:32:11Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。 我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。 特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
  論文  参考訳（メタデータ） (2022-06-15T18:20:01Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)

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

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