抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
最大カバレージ問題において,整数kとともに,母集団[n]の部分集合T_1,すなわちT_mを与え,その目的は,C(S):Big|cup_i||ST_iBig|を最大化するサイズkの部分集合S→∞[m]を見つけることである。この問題に対する greedy欲アルゴリズムが1e ̄-1の最適近似比を達成するという古典的な結果である。本研究では,要素aがカバーされる回数に依存する量によって寄与できるこの問題の一般化を考察した。凹形,非減少関数φを与えられた場合,C ̄φ(S):=Σ_a||[n]w_aφ(|S|_a)を定義し,|S|_a=||||S:||T_i}|である。標準最大被覆率問題は,φ(j)=min{j,1}を取ることに対応する。このようなφに対して,著者らは,α_φ:=min_x|ΔN ̄*E[φ(Poi(x))]/φ(E[Poi(x)])によって定義される,φのPoisson共振器比に等しい近似比を達成する効率的なアルゴリズムを提供した。この近似保証を補完して,φがサブ線形的に成長するとき,マッチングNP-硬度結果を確立した。特殊ケースとして,著者らは,独特のゲーム予測に基づく,最大マルチカバレージに関する[Barmanら,IPCO,2020]の結果を改善し,幾何学的に支配的な規則のための多勝者承認ベース投票に関する[Dudyczら,IJCAI,2020]の結果を回復する。これらの結果は,これらの特別なケースを超え,分散資源配分問題,福祉最大化問題,および一般ルールのための承認ベース投票への応用で,それを説明する。【JST・京大機械翻訳】