論文の概要: Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
- arxiv url: http://arxiv.org/abs/2512.03419v1
- Date: Wed, 03 Dec 2025 03:54:20 GMT
- ステータス: 情報取得中
- システム内更新日: 2025-12-04 12:04:44.003528
- Title: Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
- Title（参考訳）: インスタンス空間解析を用いた最大傾き問題のアルゴリズム性能評価と予測
- Authors: Bharat Sharman, Elkafi Hassini,
- Abstract要約: 本研究では, インスタンス空間解析(ISA)手法を用いて, 最先端(SOTA)アルゴリズムの性能を評価・予測する。
データセットは、TWITTER、COLLAB、BINARYベンチマークからグラフインスタンスを使用してコンパイルされた。
ISAベースのアルゴリズム性能予測モデルは、BHOSLIBデータセットとDIMACSデータセットからコンパイルされた34の挑戦的なテストインスタンス上で実行される。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The maximum clique problem, a well-known graph-based combinatorial optimization problem, has been addressed through various algorithmic approaches, though systematic analyses of the problem instances remain sparse. This study employs the instance space analysis (ISA) methodology to systematically analyze the instance space of this problem and assess & predict the performance of state-of-the-art (SOTA) algorithms, including exact, heuristic, and graph neural network (GNN)-based methods. A dataset was compiled using graph instances from TWITTER, COLLAB and IMDB-BINARY benchmarks commonly used in graph machine learning research. A set of 33 generic and 2 problem-specific polynomial-time-computable graph-based features, including several spectral properties, was employed for the ISA. A composite performance mea- sure incorporating both solution quality and algorithm runtime was utilized. The comparative analysis demonstrated that the exact algorithm Mixed Order Maximum Clique (MOMC) exhib- ited superior performance across approximately 74.7% of the instance space constituted by the compiled dataset. Gurobi & CliSAT accounted for superior performance in 13.8% and 11% of the instance space, respectively. The ISA-based algorithm performance prediction model run on 34 challenging test instances compiled from the BHOSLIB and DIMACS datasets yielded top-1 and top-2 best performing algorithm prediction accuracies of 88% and 97%, respectively.
- Abstract（参考訳）: グラフに基づく組合せ最適化問題としてよく知られた最大傾き問題は、様々なアルゴリズムアプローチを通じて解決されてきたが、問題事例の体系的解析は依然として不十分である。
本研究では、この問題のインスタンス空間を系統的に解析し、精度、ヒューリスティック、グラフニューラルネットワーク(GNN)に基づく手法を含む最先端(SOTA)アルゴリズムの性能を評価し予測する。
データセットは、TWITTER、COLLAB、IMDB-BINaryベンチマークからグラフインスタンスを使用してコンパイルされた。
ISAには、いくつかのスペクトル特性を含む33の一般および2つの問題固有の多項式時間計算可能なグラフベースの特徴が採用された。
ソリューション品質とアルゴリズムランタイムの両方を組み込んだ複合性能のメア・クオリティが利用された。
比較分析の結果、Mixed Order Maximum Clique (MOMC) はコンパイルされたデータセットによって構成されたインスタンス空間の約74.7%で優れた性能を示した。
GurobiとCliSATは、それぞれインスタンス空間の13.8%と11%で優れたパフォーマンスを誇った。
ISAベースのアルゴリズム性能予測モデルは、BHOSLIBデータセットとDIMACSデータセットからコンパイルされた34の挑戦的なテストインスタンス上で実行される。
関連論文リスト
- Landscape Features in Single-Objective Continuous Optimization: Have We Hit a Wall in Algorithm Selection Generalization? [4.510532471907222]
本研究では,異なる問題表現に基づくASモデルの一般化可能性を評価する。
また,最近提案されたトポロジカルランドスケープ解析機能と同様に,最も広く利用されているランドスケープ解析機能についても検討している。
論文 参考訳（メタデータ） (2025-01-29T14:03:27Z) - Exploratory Landscape Analysis for Mixed-Variable Problems [0.7252027234425334]
決定空間が連続変数、バイナリ変数、整数変数、カテゴリー変数の混合である混合変数問題に対する探索的景観特徴を計算する手段を提供する。
実用化のためのメリットをさらに強調するため,自動アルゴリズム選択研究を設計・実施する。
トレーニングされたアルゴリズムセレクタは、すべてのベンチマーク問題に対して、単一のベストと仮想ベストのギャップを57.5%縮めることができる。
論文 参考訳（メタデータ） (2024-02-26T10:19:23Z) - Analyzing the Capabilities of Nature-inspired Feature Selection
Algorithms in Predicting Student Performance [0.0]
本稿では,学生のパフォーマンス予測に使用するアンサンブルアルゴリズムの特徴選択部分において,自然に触発されたアルゴリズムの相対的性能について分析を行った。
その結果,自然に着想を得たアルゴリズムを特徴選択に利用し,従来のMLアルゴリズムを分類に利用することで,予測精度が向上し,特徴セットのサイズを最大65%削減できることがわかった。
論文 参考訳（メタデータ） (2023-08-15T21:18:52Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - SELECTOR: Selecting a Representative Benchmark Suite for Reproducible
Statistical Comparison [0.7046417074932257]
最適化アルゴリズムの比較に係わるべき多様な問題事例を選択するための3つのアプローチを評価する。
最初のアプローチでは、クラスタリングを使用して、問題インスタンスの類似したグループを特定し、その後、各クラスタからサンプリングして、新しいベンチマークを構築する。
他の2つのアプローチは、支配的および最大独立なノード群を特定するためにグラフアルゴリズムを使用する。
論文 参考訳（メタデータ） (2022-04-25T09:38:43Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。