Constant Ratio Approximation Algorithms for Weighted Single Container Packing

• Item type: SIG Technical Reports(1)
• 公開日: 2005-11-11
• タイトル: Constant Ratio Approximation Algorithms for Weighted Single Container Packing
• タイトル / 言語: en
• タイトル: Constant Ratio Approximation Algorithms for Weighted Single Container Packing
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Informatics Kyoto University Fachbereich Informatik Universitat Dortmund
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University, Fachbereich Informatik Universitat Dortmund
• 著者名: Rolf, Harren
• 著者名(英): Rolf, Harren
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Given a set of rectangular three-dimensional items all of them associated with a profit and a single bigger rectangular three-dimensional bin we can ask to find a non-rotational non-overlapping packing of a selection of these items into the bin to maximize the profit. This problem differs from three-dimensional strip- and bin-packing as we are to pack into a single bounded him. We derive a (16 + e)-approximation algorithm improve the algorithm to an approximation ratio of (9 + e).
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a set of rectangular three-dimensional items, all of them associated with a profit, and a single bigger rectangular three-dimensional bin, we can ask to find a non-rotational, non-overlapping packing of a selection of these items into the bin to maximize the profit. This problem differs from three-dimensional strip- and bin-packing as we are to pack into a single bounded him. We derive a (16 + e)-approximation algorithm improve the algorithm to an approximation ratio of (9 + e).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 110(2005-AL-103), p. 49-56, 発行日 2005-11-11
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会