制約のないサブモジュラー最大化に対する厳密な線形時間(1/2)近似

制約のないサブモジュラー最大化問題を考えます。この問題では、非負のサブモジュラー関数 f : 2 N → ℝ + が与えられ、目的は f(S) を最大化する部分集合 S ⊆ N を見つけることです。これは最も基本的なサブモジュラー最適化問題のひとつであり、広範な応用を持っています。制約のないサブモジュラー最大化に捕らえられるよく知られた問題には、MaxCut、Max-DiCut、および Max-SAT や最大施設配置の変種が含まれます。私たちは、1/2 の厳密な近似保証を達成する単純なランダム化線形時間アルゴリズムを提示し、Feige らの知られている困難さの結果に一致します。私たちのアルゴリズムは、問題の特定の対称性を利用した貪欲法の適応に基づいています。私たちの方法は直感に反するように思えるかもしれませんが、問題に対する貪欲アルゴリズムが有界近似因子を達成できないことが知られています。