凹面被覆問題のためのタイト近似保証【JST・京大機械翻訳】

Barman Siddharth; Fawzi Omar; Ferme Paul

プレプリント

J-GLOBAL ID：202202219839306470 整理番号：21P0052042

凹面被覆問題のためのタイト近似保証【JST・京大機械翻訳】

Tight Approximation Guarantees for Concave Coverage Problems

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年10月02日プレプリントサーバーでの情報更新日： 2021年01月18日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

最大カバレージ問題において,整数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・京大機械翻訳】

, , , , , , , , , , , , , ,

ネットワーク法 , 信号理論 , 数値計算 , 計算理論 , グラフ理論基礎

, , ,

前のページに戻る