Daily Arxiv

世界中で発行される人工知能関連の論文をまとめるページです。
このページはGoogle Geminiを活用して要約し、非営利で運営しています。
論文の著作権は著者および関連機関にあり、共有する際は出典を明記してください。

Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem

Created by
  • Haebom

作者

Vanja Stojanovi c、Bor Panger\v{s}i\v{c}

概要

本論文は、NP-complete問題である相互可視性(Mutual Visibility、MV)問題の実証的分析を行います。既存の研究は理論的研究に焦点を当てていましたが、実際の動作の実験的分析は不足していました。この論文は、直接ランダムヒューリスティック、ハイパーグラフベースの近似アルゴリズム、遺伝的アルゴリズムの3つのアルゴリズムを、さまざまな合成グラフデータセット(分析的に知られているμ(G)値を持つデータセット、および一般的なグラフモデルを含む)に適用して評価します。その結果、小さなグラフではアルゴリズムが理論的境界と一致するMV集合サイズを達成しますが、大きなグラフでは理論的限界とかなりの違いを示しました。厳しい境界がないという点と組み合わせると、絶対的な品質評価は困難ですが、既知の最適グラフの検証の結果、遺伝的アルゴリズムと他のヒューリスティックアルゴリズムが実験的に最高のパフォーマンスを示しました。

Takeaways、Limitations

Takeaways:
相互可視性問題に対する3つのアルゴリズムの実証的性能比較分析を提供する。
小さなグラフでは、アルゴリズムが理論的境界に一致する結果を示しています。
遺伝的アルゴリズムが実験的に最高の性能を示したことを確認する。
Limitations:
大きなグラフでは、アルゴリズムの結果は理論的限界とかなりの違いを示しています。
厳格な理論的境界がないため、絶対的な年の質を評価することは困難です。
👍