論文の概要: Advanced Kernel Search approach for the MST Problem with conflicts involving affinity detection and initial solution construction
- arxiv url: http://arxiv.org/abs/2401.02222v2
- Date: Tue, 10 Jun 2025 16:39:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-11 15:11:38.356103
- Title: Advanced Kernel Search approach for the MST Problem with conflicts involving affinity detection and initial solution construction
- Title（参考訳）: 親和性検出と初期解構築を含む競合を伴うMST問題に対する高度なカーネルサーチ手法
- Authors: Francesco Carrabs, Martina Cerulli, Domenico Serra,
- Abstract要約: 我々は,最小スパンニング木問題と衝突を解くために,改良されたカーネルサーチ手法を用いる。
競合グラフからの独立集合の計算をアルゴリズムに統合し、親和性を検出し、競合を効果的に管理する。
提案手法はMSTC向けに設計されているが,その原理は競合を伴う他の最適化問題にまで拡張することができる。
- 参考スコア（独自算出の注目度）: 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 an enhanced Kernel Search method, which iteratively solves refined problem restrictions. Our approach addresses two central open questions in the kernel search literature: (1) how to determine the affinity between variables to ensure that the restricted problem contains variables that are as compatible as possible, meaning they are more likely to appear together in a feasible solution, and (2) how to construct an initial feasible solution quickly. To this end, we integrate the computation of independent sets from the conflict graph within the algorithm to detect affinities and effectively manage conflicts. Furthermore, we heuristically construct an initial starting point, significantly accelerating the computational process. Although our methodology is designed for MSTC, its principles could be extended to other combinatorial optimization problems with conflicts. Experimental results on benchmark instances demonstrate the efficiency and competitiveness of our approach compared to existing methods in the literature, achieving 17 new best-known values.
- Abstract（参考訳）: 競合を持つ最小スパンニングツリー問題(Minimum Spanning Tree Problem with Conflicts)は、グラフの最小の競合のないスパンニングツリー、すなわち最小コストのスパンニングツリーを見つけることである。
本稿では,改良されたカーネル探索法を用いて,改良された問題制約を反復的に解決する手法を提案する。
提案手法は,(1)変数間の親和性を決定することによって,制限された問題に可能な限り互換性のある変数が存在することを保証する方法,(2)初期実現可能な解を迅速に構築する方法,の2点に対処する。
この目的のために,アルゴリズム内にコンフリクトグラフから独立した集合の計算を統合し,親和性を検出し,競合を効果的に管理する。
さらに,初期開始点をヒューリスティックに構築し,計算処理を著しく高速化する。
提案手法はMSTC向けに設計されているが,その原理は競合を伴う他の組合せ最適化問題にまで拡張することができる。
ベンチマーク実験の結果,文献の既存手法と比較して,提案手法の効率性と競争性を実証し,新たに17個の評価値を得た。
関連論文リスト
- Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。