文献

J-GLOBAL ID：202202261575084711   整理番号：22A0802578

一般化拡張可能ビンパッキング問題のための近似法【JST・京大機械翻訳】

Approximation Schemes for the Generalized Extensible Bin Packing Problem

著者 (1件)： Levin Asaf (Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel)
資料名： Algorithmica  (Algorithmica)
巻： 84  号： 2  ページ： 325-343  発行年： 2022年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 不等なビンサイズ問題を有する拡張可能ビンパッキングの新しい一般化を提示した。この一般化において,ビンサイズを超えるコスト(ビン容量としても知られる)はビンの指数に依存し,ビンの大きさが超過する量に依存する。この一般化は,不等なビンサイズ問題を有する拡張可能なビンパッキングのための既存の多項式時間近似方式(PTAS)を提示するために使用されたコスト関数に関する仮定を満足しない。本研究では,この新一般化のための効率的なPTAS(EPTAS)の存在を示し,特に,EPTASに不等なビンサイズ問題を有する拡張可能ビンパッキングのための以前のPTASを改善した。この新しいスキームは,シフト技術とそれに続く多項式数n倍プログラミングインスタンスの解に基づいている。さらに,問題の関連するビンパッキング型バリアントに対する漸近完全多項式時間近似スキームを提示した。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  スケジューリング ,  容量 ,  *近似法 ,  費用関数 ,  *ビンパッキング問題
準シソーラス用語： 多項式時間 ,  完全多項式時間近似スキーム , 【Automatic Indexing@JST】

著者キーワード (4件)： スケジューリング ,  負荷バランス ,  近似スキーム ,  n-Foldプログラミング

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (4件)： 一般化 ,  拡張 ,  ビンパッキング問題 ,  近似法