論文の概要: Improved Exact and Heuristic Algorithms for Maximum Weight Clique

• arxiv url: http://arxiv.org/abs/2302.00458v1
• Date: Wed, 1 Feb 2023 14:02:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-02 17:25:20.679504
• Title: Improved Exact and Heuristic Algorithms for Maximum Weight Clique
• Title（参考訳）: 最大重量傾きに対する実効性およびヒューリスティックアルゴリズムの改良
• Authors: Roman Erhardt, Kathrin Hanauer, Nils Kriege, Christian Schulz, Darren Strash
• Abstract要約: 最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。 提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。 我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 1.2074552857379273
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interleave successful techniques from related work with novel data reduction rules that use local graph structure to identify and remove vertices and edges while retaining the optimal solution. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs. Our data reductions always produce smaller reduced graphs than existing data reductions alone. As a result, our exact algorithm, MWCRedu, finds solutions orders of magnitude faster on naturally weighted, medium-sized map labeling graphs and random hyperbolic graphs. Our heuristic algorithm, MWCPeel, outperforms its competitors on these instances, but is slightly less effective on extremely dense or large instances.
• Abstract（参考訳）: 多くの応用でグラフ理論においてよく知られた問題である最大重量傾き問題を解くための改良された精度とヒューリスティックなアルゴリズムを提案する。 提案アルゴリズムは,局所的なグラフ構造を用いて最適な解を維持しながら頂点と辺を識別・除去する,新しいデータ還元規則を用いた手法を応用した。 我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力においてその技術の現状よりも優れていることを示す。 我々のデータリダクションは、既存のデータリダクションだけでなく、グラフを小さくする。 その結果、我々の正確なアルゴリズムMWCReduは、自然重み付き中規模の地図ラベリンググラフとランダムな双曲グラフで解のオーダーを桁違いに高速化する。 私たちのヒューリスティックアルゴリズムであるMWCPeelは、これらのインスタンスで競合他社より優れていますが、非常に密度の高いインスタンスや大きめのインスタンスでは若干効果がありません。

関連論文リスト

• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• FORBID: Fast Overlap Removal By stochastic gradIent Descent for Graph Drawing [1.1470070927586014]
  ノード間のオーバーラップは、グラフの可視化の可読性を妨げます。 オーバーラップ除去(OR)アルゴリズムはレイアウト後処理として提案されている。 共同応力およびスケーリング最適化問題として,新しい勾配モデルORを提案する。
  論文  参考訳（メタデータ） (2022-08-19T13:51:44Z)
• CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
  グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。 グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。 この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
  論文  参考訳（メタデータ） (2022-08-01T17:34:07Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。 我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。 特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
  論文  参考訳（メタデータ） (2022-06-15T18:20:01Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。 LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
  論文  参考訳（メタデータ） (2022-05-20T11:54:03Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。 現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。 我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
  論文  参考訳（メタデータ） (2021-11-09T19:18:18Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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