論文の概要: Optimizing Minimum Vertex Cover Solving via a GCN-assisted Heuristic Algorithm

• arxiv url: http://arxiv.org/abs/2503.06396v1
• Date: Sun, 09 Mar 2025 02:31:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-11 15:49:43.482848
• Title: Optimizing Minimum Vertex Cover Solving via a GCN-assisted Heuristic Algorithm
• Title（参考訳）: GCN支援ヒューリスティックアルゴリズムによる最小頂点被覆解の最適化
• Authors: Enqiang Zhu, Qiqi Bao, Yu Zhang, Chanjuan Liu,
• Abstract要約: 本稿では,大規模グラフにおけるMVC問題の解法としてGCNIVCを提案する。 GCNIVCは、精度と効率の両面で最先端のMVCアルゴリズムより優れていることを示す。
• 参考スコア（独自算出の注目度）: 5.235311531581293
• License:
• Abstract: The problem of finding a minimum vertex cover (MVC) in a graph is a well-known NP-hard problem with significant practical applications in optimization and scheduling. Its complexity, combined with the increasing scale of problems, underscores the need for efficient and effective algorithms. However, existing heuristic algorithms for MVC often rely on simplistic initialization strategies and overlook the impact of edge attributes and neighborhood information on vertex selection. In this paper, we introduce GCNIVC, a novel heuristic search algorithm designed to address the limitations of existing methods for solving MVC problems in large-scale graphs. Our approach features two main innovations. First, it utilizes a Graph Convolutional Network (GCN) to capture the global structure of graphs, which enables the generation of high-quality initial solutions that enhance the efficiency of the subsequent search process. Second, GCNIVC introduces a new heuristic that employs three containers and the concept of double-covered edges (dc-edges), improving search efficiency and providing greater flexibility for adding and removing operations based on edge attributes. Through extensive experiments on benchmark datasets, we demonstrate that GCNIVC outperforms state-of-the-art MVC algorithms in terms of both accuracy and efficiency. Our results highlight the effectiveness of GCNIVC's GCN-assisted initialization and its edge-informed search strategy. This study not only advances the understanding of MVC problem-solving but also contributes a new tool for addressing large-scale graph optimization challenges.
• Abstract（参考訳）: グラフ内の最小頂点被覆(MVC)を見つける問題は、最適化とスケジューリングにおいて重要な実用的応用を持つよく知られたNPハード問題である。 その複雑さと問題の大きさの増大が組み合わさって、効率的で効率的なアルゴリズムの必要性を浮き彫りにしている。 しかし、MVCの既存のヒューリスティックアルゴリズムは、しばしば単純化された初期化戦略に依存し、エッジ属性や周辺情報が頂点選択に与える影響を見落としている。 本稿では,大規模グラフにおけるMVC問題を解くための既存の手法の限界に対処するために設計された,新しいヒューリスティック検索アルゴリズムであるGCNIVCを紹介する。 このアプローチには2つの大きな革新があります。 まず、グラフ畳み込みネットワーク(GCN)を用いてグラフのグローバル構造をキャプチャし、その後の探索プロセスの効率を高める高品質な初期解を生成する。 第二に、GCNIVCは3つのコンテナと二重被覆エッジ(dc-edges)の概念を採用し、検索効率を改善し、エッジ属性に基づいた操作の追加と削除のための柔軟性を提供する新しいヒューリスティックを導入した。 ベンチマークデータセットに関する広範な実験を通じて、GCNIVCは精度と効率の両面で最先端のMVCアルゴリズムより優れていることを示した。 本研究はGCNIVCのGCN支援初期化とエッジインフォームド検索戦略の有効性を強調した。 この研究はMVC問題解決の理解を深めるだけでなく、大規模グラフ最適化の課題に対処するための新しいツールにも貢献する。

関連論文リスト

• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks [37.41604955004456]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において顕著な成功を収めている。 GNNを大規模グラフのアプリケーションに拡張するための様々なサンプリング手法が提案されている。
  論文  参考訳（メタデータ） (2024-10-07T18:29:02Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。 CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。 詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
  論文  参考訳（メタデータ） (2024-06-11T10:12:10Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
  論文  参考訳（メタデータ） (2023-02-03T07:15:37Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)

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

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