抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ROUND-UFPとROUND-SAP,古典的BIN PACKING問題の2つの一般化,経路(UFP)と貯蔵割当問題(SAP)に関する非分割フロー問題に対応する。筆者らは,そのエッジと各タスクに対して要求とサブパスを与えるタスクのセットに容量を持つ経路を与えた。ROUND-UFPにおいて,目標は,各コピーに対して,与えられた経路の最小数コピー(ラウンド)へのすべてのタスクのパッキングを見つけることであり,任意のエッジ上のタスクの全要求は,それぞれのエッジの容量を超えない。ROUND-SAPでは,タスクは長方形であり,目標は,すべての長方形がエッジの容量プロファイルを完全に下回るように,これらの長方形の最少数にこれらの長方形の非重複充填を見つけることである。BIN PACKINGとは対照的に,両問題は,全てのエッジ容量が等しい場合でも,漸近多項式時間近似スキーム(APTAS)をアドミットしないことを示した。しかし,この設定では,両問題に対して漸近(2+ε)近似を得た。一般的事例に対して,著者らは,両方の問題に対して,(1+δ)-資源増強の下で,O(loglogn)近似アルゴリズムおよびO(loglog1/δ)近似を得た。非ボトルネック仮定(すなわち,最大タスク要求が最小エッジ容量)の中間設定に対して,ROUND-UFPおよびROUND-SAPに対する絶対12および漸近(16+ε)近似アルゴリズムを得た。【JST・京大機械翻訳】
