サイズ制約下における非単調DR-サブモジュラーマキシマイゼーションのための高速近似アルゴリズム

この記事では、サイズ制約$k$の下で非単調DR-サブモジュラーマキシマイゼーションを扱う。著者は、この問題を解決するための2つの近似アルゴリズム、FastDrSubとFastDrSub++を提案している。FastDrSubは、近似比率$0.044$を提供し、クエリ複雑度は$O(n ext{ log}(k))$である。FastDrSub++は、入力パラメータ$ ext{ε} > 0$に対して、近似比率$1/4 - ext{ε}$を実現し、クエリ複雑度も$(n ext{ log } k)$で改善されている。これにより、提案されたアルゴリズムは、低複雑度の$O(n ext{ log }(k))$で問題に対する初の定数比率の近似アルゴリズムである。さらに、実験的評価も行い、既存の最新技術と比較することで、クエリ複雑度と解の質の両面で提案されたアルゴリズムが優れていることを示している。