Fugu-MT 論文翻訳(概要): Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs

論文の概要: Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs

arxiv url: http://arxiv.org/abs/2401.02222v1
Date: Thu, 4 Jan 2024 12:10:39 GMT
ステータス: 処理完了
システム内更新日: 2024-03-18 10:39:12.015840
Title: Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs
Title（参考訳）: 対立するエッジペアを持つ最小スパンニングツリー問題のカーネルサーチによる解法
Authors: Francesco Carrabs, Martina Cerulli, Domenico Serra,
Abstract要約: 本稿では,カーネルサーチ手法を用いて,最小スパンニング木問題と競合を解消する。このアプローチの主な新規性は、アルゴリズム内でコンフリクトグラフの独立したセットを使用することである。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Minimum Spanning Tree Problem with Conflicts consists in finding the minimum conflict-free spanning tree of a graph, i.e., the spanning tree of minimum cost, including no pairs of edges that are in conflict. In this paper, we solve this problem using a tailored Kernel Search heuristic method, which consists in solving iteratively improved restrictions of the problem. The main novelty of the approach consists in using an independent set of the conflict graph within the algorithm. We test our approach on the benchmark instances and we compare our results with the ones obtained by other heuristics available in the literature.
Abstract（参考訳）: 競合を持つ最小スパンニングツリー問題(Minimum Spanning Tree Problem with Conflicts)は、グラフの最小の競合のないスパンニングツリー、すなわち最小コストのスパンニングツリーを見つけることである。本稿では,この問題の反復的に改善された制約を解消するカーネル探索ヒューリスティック手法を用いて,この問題を解決する。このアプローチの主な新規性は、アルゴリズム内でコンフリクトグラフの独立したセットを使用することである。提案手法をベンチマークインスタンス上でテストし,本論文で利用可能な他のヒューリスティックスと結果を比較した。

関連論文リスト

Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
本稿では,最短経路問題とSteiner木問題に焦点をあてる。我々は、スコアリングモデルを構築するための実現可能な仮説空間の設計に関する理論的知見を提供する。実験により,そのような問題を統計的に有意な程度に解決できることが示唆された。
論文参考訳（メタデータ） (2024-02-03T17:05:01Z)
Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文参考訳（メタデータ） (2023-12-19T13:17:43Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。解法の効率は、分割する変数を選択するのに使用される分岐に依存する。分岐を効率的に学習できる強化学習法を提案する。
論文参考訳（メタデータ） (2023-06-09T14:01:26Z)
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)
Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文参考訳（メタデータ） (2022-08-25T10:31:00Z)
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)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
論文参考訳（メタデータ） (2020-10-22T08:33:58Z)
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文参考訳（メタデータ） (2020-04-25T05:45:59Z)

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