日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

グラフ最適化arXiv:2606.13834

Δ探索を用いた部分グラフ抽出問題の解法

Solving Subgraph Extraction Problems Using $Δ$Search

シェア:XThreadsFacebookLINEはてブBluesky

NP困難な部分グラフ抽出問題を解くための汎用ヒューリスティックフレームワークΔ探索を提案し、様々なグラフ問題で既存手法と同等以上の性能を示した。

詳しい要約

1. どんなもの?

- 多くのNP-hardグラフ問題を最適部分グラフ抽出問題としてモデル化 - ネットワーク設計、施設配置、ロボティクス、グラフ描画などに共通するパターン - ドメイン固有のヒューリスティクスではなく、一般的で高速なヒューリスティックフレームワーク $Δ$Search を提案 - ユーザーは実現可能性制約と最適性基準を提供するだけで利用可能 - 厳密解法に組み込むことで探索空間の積極的な枝刈りにより性能向上も可能

2. 先行研究と比べてどこがすごい?

- 従来はドメイン固有のヒューリスティクスが主流 - $Δ$Search は一般的なフレームワークでありながら、MPS、UFLP、PCVC で最先端ヒューリスティクスと同等以上の性能を同程度の実行時間で達成 - 他の問題では問題固有のチューニングなしで最先端アルゴリズムの約89%の解品質を達成 - 厳密解法の性能向上にも利用可能

3. 技術・手法の肝は?

- Reward-Penalty optimization の洞察を活用 - ユーザーが実現可能性制約と最適性基準を提供するだけで部分グラフ抽出問題を表現 - 一般的で高速なヒューリスティックフレームワーク - 厳密解法に組み込むことで探索空間の積極的な枝刈りを実現

4. どうやって有効だと検証した?

- 単調グラフ問題: Maximum Planar Subgraph (MPS)、Minimum Connected Dominating Set - 重み付き単調問題: Maximum Weighted Independent Set、Minimum Weighted Steiner Tree - 非単調グラフ問題: Prize Collecting Vertex Cover (PCVC)、Uncapacitated Facility Location Problem (UFLP) - これらの問題で評価し、MPS、UFLP、PCVC では最先端ヒューリスティクスと同等以上、他では約89%の解品質を達成

5. 議論はある?

- 要旨からは不明

6. 次に読むべき論文は?

- Maximum Planar Subgraph (MPS) - Minimum Connected Dominating Set - Maximum Weighted Independent Set - Minimum Weighted Steiner Tree - Prize Collecting Vertex Cover (PCVC) - Uncapacitated Facility Location Problem (UFLP)

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Rebin Silva Valan Arasu, Rajiv Gupta

分類: cs.PF, cs.DC, eess.SY

原文アブストラクト

Many NP-hard graph problems can be modeled as optimal subgraph extraction problems with feasibility constraints. From Network Design to Facility Location, from Robotics to Graph Drawing, the subgraph extraction pattern emerges across diverse domains. Despite this commonality, these problems are typically solved with domain-specific heuristics. Usually, these problems balance competing objectives such as maximizing coverage or minimizing cost while satisfying structural constraints such as connectivity, planarity and reachability. In this work, we introduce $Δ$Search, a general and fast heuristic framework that exploits the insight of Reward-Penalty optimization for solving a large class of subgraph extraction problems. The framework is easy to use as it only requires feasibility constraints and optimality criteria to be provided by the user to express the subgraph extraction problem. We also show how exact methods can be augmented with $Δ$Search to improve their performance by aggressive pruning of the search space. We evaluate our framework on monotone graph problems such as Maximum Planar Subgraph (MPS) and Minimum Connected Dominating Set, Weighted Monotone problems such as Maximum Weighted Independent Set and Minimum Weighted Steiner Tree, and non-monotone graph problems such as Prize Collecting Vertex Cover (PCVC) and Uncapacitated Facility Location Problem (UFLP). Our results show that $Δ$Search matches or surpasses state of the art heuristics for MPS, UFLP and PCVC problems with similar runtime. For the remaining problems, $Δ$Search achieves approximately 89% of the solution quality of the state-of-the-art algorithms without any problem-specific tuning

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  3. 3newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI