論文の概要: Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem

• arxiv url: http://arxiv.org/abs/2507.01076v1
• Date: Tue, 01 Jul 2025 14:35:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-03 14:22:59.837731
• Title: Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem
• Title（参考訳）: 相互可視性問題に対するヒューリスティックおよび近似アルゴリズムの実証解析
• Authors: Vanja Stojanović, Bor Pangeršič,
• Abstract要約: NP完全相互可視問題に対する3つのアルゴリズムの実装と評価を行った。 以上の結果から,より小さなグラフに対して,アルゴリズムは理論的境界に整合したMV集合のサイズを一貫して達成することを示した。 既知の最適グラフの検証では、遺伝的アルゴリズムと他のアルゴリズムが試験方法の中で最高の性能を示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms - a direct greedy heuristic, a hypergraph-based approximation, and a genetic algorithm - on diverse synthetic graph datasets, including those with analytically known $\mu(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods.
• Abstract（参考訳）: NP完全相互可視性(MV)問題は現在、理論的研究にもかかわらず、その実践行動に関する実証的な分析を欠いている。 本稿では, 解析的に知られている$\mu(G)$値や一般グラフモデルを含む, 多様な合成グラフデータセット上に, 直接グリーディヒューリスティック, ハイパーグラフに基づく近似, 遺伝的アルゴリズムの3つの異なるアルゴリズムを実装・評価することで, このギャップを解消する。 以上の結果から,より小さなグラフに対して,アルゴリズムは理論的境界に整合したMV集合のサイズを一貫して達成することを示した。 しかし、より大きな場合において、解のサイズは特に理論上の限界から分岐するが、これは厳密な境界の欠如と相まって絶対的な品質評価を複雑にする。 それでも、既知の最適グラフの検証は、遺伝的アルゴリズムと他のヒューリスティックが試験方法の中で最もよく機能することを示した。

関連論文リスト

• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
  最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。 様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。 以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
  論文  参考訳（メタデータ） (2024-09-26T12:50:00Z)
• Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
  本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。 アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
  論文  参考訳（メタデータ） (2024-05-18T17:38:25Z)
• On the Finite-Time Performance of the Knowledge Gradient Algorithm [1.713291434132985]
  知識勾配(KG)アルゴリズムは、ベストアーム識別(BAI)問題に対して人気があり効果的なアルゴリズムである。 KGアルゴリズムの有限時間性能に関する新しい理論的結果を示す。
  論文  参考訳（メタデータ） (2022-06-14T13:42:05Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
  本研究では,Threshold Learned Iterative Shrinkage Algorithming (NLISTA)を導入することでギャップを埋める。 合成データを用いた実験は理論結果と相関し,その手法が最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-26T11:31:08Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。