学習拡張最大独立集合

一般グラフにおける最大独立集合（MIS）問題を、学習拡張アルゴリズムの枠組み内で研究します。MIS問題はNP困難であり、任意の>0に対してn^1-まで近似することもNP困難であることが知られています。我々は、固定されたMISに対する頂点メンバーシップクエリに回答する機械学習モデルから得られたオラクルの存在下で、この障壁を打破できることを示します。最初に考慮する設定では、オラクルは各頂点に対して1回クエリされ、頂点が固定されたMISに属するかどうかを知ることができ、オラクルは確率1/2 +で正しい答えを返します。この設定の下で、グラフの最大次数をとしたときにO (/) -近似をO (m)時間で得るアルゴリズムを示します。2番目の設定では、各頂点に対してオラクルに複数回のクエリを許可し、各々のクエリは確率1/2 +で正しいです。この設定について、O (n/²)の合計クエリとO (m)の実行時間を使用するO (1) -近似アルゴリズムを示します。