単調劣モジュラ多重ナップサックのためのほぼ最適な近似アルゴリズム【JST・京大機械翻訳】

Fairstein Yaron; Kulik Ariel; Joseph; Naor; Raz Danny; Shachnai Hadas

プレプリント

J-GLOBAL ID：202202209879391882 整理番号：21P0030125

単調劣モジュラ多重ナップサックのためのほぼ最適な近似アルゴリズム【JST・京大機械翻訳】

An Almost Optimal Approximation Algorithm for Monotone Submodular Multiple Knapsack

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

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

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

多重Knapsack制約を受ける単調サブモジュール関数を最大化する問題を研究した。入力は,アイテムのセットIであり,それぞれは,非負重みを持ち,任意の容量のビンの集合である。また,アイテムの部分集合上で,サブモジュール,単調,および非負関数fを与えた。目的は,f(A)が最大化されるようなビンにおけるアイテムA⊆Iの部分集合のパッキングを見つけることである。著者等の主な結果は,任意のΔΨ0に対して,問題に対するほぼ最適な多項式時間(1e ̄-1-ε)近似アルゴリズムである。アルゴリズムは,一般的多重ナップサック制約を制約に変換する構造化技術に依存し,そこでは,ビンを,均一容量のビンから成る,指数的に増加する基数のグループに分割する。ナップサック制約を受けるサブモジュール最適化のための技法の精密化解析と構造化を結合することにより,結果を導いた。【JST・京大機械翻訳】

, , ,
, , , , 【Automatic Indexing@JST】

数値計算 , 数値解析,近似法 , その他のオペレーションズリサーチの手法 , 数理計画法 , 計算理論

, , ,

前のページに戻る