Fugu-MT 論文翻訳(概要): Learning to Prune Instances of Steiner Tree Problem in Graphs

論文の概要: Learning to Prune Instances of Steiner Tree Problem in Graphs

arxiv url: http://arxiv.org/abs/2208.11985v1
Date: Thu, 25 Aug 2022 10:31:00 GMT
ステータス: 処理完了
システム内更新日: 2022-08-26 13:19:57.438645
Title: Learning to Prune Instances of Steiner Tree Problem in Graphs
Title（参考訳）: グラフにおけるシュタイナー木問題のpruneインスタンスへの学習
Authors: Jiwei Zhang and Deepak Ajwani
Abstract要約: ノードの集合が与えられるグラフ上のスタイナー木問題を考える。目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
参考スコア（独自算出の注目度）: 0.47138177023764655
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes. This is a classical NP-hard combinatorial optimisation problem. In recent years, a machine learning framework called learning-to-prune has been successfully used for solving a diverse range of combinatorial optimisation problems. In this paper, we use this learning framework on the Steiner tree problem and show that even on this problem, the learning-to-prune framework results in computing near-optimal solutions at a fraction of the time required by commercial ILP solvers. Our results underscore the potential of the learning-to-prune framework in solving various combinatorial optimisation problems.
Abstract（参考訳）: 我々は、ノードの集合が与えられたグラフ上のSteiner木問題を考える。その目標は、与えられた集合にすべてのノードを含む最小限の重みのツリー部分グラフを見つけることである。これは古典的なNPハード組合せ最適化問題である。近年、機械学習フレームワークであるLearning-to-pruneは、様々な組合せ最適化問題の解決に成功している。本稿では,このスタイナー木問題に関する学習フレームワークを用いて,この問題においても,学習から学習までのフレームワークが,商用のilpソルバが要求する時間にほんの少しの時間で最適に近い解を計算できることを示す。本研究は,様々な組合せ最適化問題の解法における学習から学習までの枠組みの可能性を強調した。

関連論文リスト

Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文参考訳（メタデータ） (2024-06-05T22:52:27Z)
TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。解法の効率は、分割する変数を選択するのに使用される分岐に依存する。分岐を効率的に学習できる強化学習法を提案する。
論文参考訳（メタデータ） (2023-06-09T14:01:26Z)
Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search [9.061356032792952]
グラフニューラルネットワークとモンテカルロ木探索を組み合わせたステイナツリーの計算手法について述べる。まず、部分解として入力されるグラフニューラルネットワークをトレーニングし、出力として追加される新しいノードを提案する。このニューラルネットワークはモンテカルロ探索でスタイナー木を計算するのに使用される。
論文参考訳（メタデータ） (2023-04-30T17:15:38Z)
NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems [0.0]
我々は,グラフ上の一般的な最適化問題に対して,決定過程(MDP)を定義することによって,様々な木にまたがる問題を解く新しいフレームワークであるNeuroPrimを提案する。この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小コストスパンニングツリー (MRCST) 問題、ルーティンググラフ (STP) におけるスタイナーツリー問題。
論文参考訳（メタデータ） (2022-10-22T13:49:29Z)
Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。提案手法は, 得られた解の精度を向上させることができることを示す。
論文参考訳（メタデータ） (2022-04-11T14:05:34Z)
What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文参考訳（メタデータ） (2022-01-25T17:37:34Z)
Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文参考訳（メタデータ） (2022-01-05T13:37:27Z)
Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
本稿では,スタイナーツリー問題に取り組む。低コストのSteiner木を計算するために4つの学習フレームワークを使用します。我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
論文参考訳（メタデータ） (2021-08-18T19:55:16Z)
Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。最適ではないにもかかわらず、性能は桁違いに向上することを示す。結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文参考訳（メタデータ） (2021-06-23T09:46:11Z)
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文参考訳（メタデータ） (2021-06-09T09:18:18Z)
Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。 MWPを学習するためのテキスト弱教師付きパラダイムを提案する。この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
論文参考訳（メタデータ） (2020-12-19T03:10:21Z)

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