| 講演名 | 2000/3/22 アイテムの回転を許した二次元箱詰め問題を解くオンライン近似アルゴリズム 羽田 健志, 藤田 聡, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では箱詰め問題の一種である二次元箱詰め問題を考える.通常, 箱詰め問題ではアイテムの回転は許されていないが, 我々の扱う問題では与えられた矩形状の各アイテムは90度の回転が許されている.本稿ではこのような回転を許した二次元箱詰め問題を解くオンライン近似アルゴリズムを提案する.提案するアルゴリズムでは競合比2.5624以上, 2.6112以下となる. |
| 抄録(英) | In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90 degrees. An on-line approximation algorithm is proposed. The algorithm is with worst case ratio of at least 2.5624 and at most 2.6112. |
| キーワード(和) | 二次元箱詰め問題 / オンラインアルゴリズム / 回転可能なアイテム |
| キーワード(英) | two-dimensional bin-packing / on-line algorithm / rotatable items |
| 資料番号 | COMP99-81 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/3/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | アイテムの回転を許した二次元箱詰め問題を解くオンライン近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An On-Line Approximation Algorithm for Two-Dimensional Bin Packing Problem with Rotatable Items |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 二次元箱詰め問題 / two-dimensional bin-packing |
| キーワード(2)（和/英） | オンラインアルゴリズム / on-line algorithm |
| キーワード(3)（和/英） | 回転可能なアイテム / rotatable items |
| 第 1 著者 氏名（和/英） | 羽田 健志 / Takeshi Hada |
| 第 1 著者 所属（和/英） | 広島大学工学部第二類(電気系) Electrical Engineering, Faculty of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 藤田 聡 / Satoshi Fujita |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類(電気系) Electrical Engineering, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 2000/3/22 |
| 資料番号 | COMP99-81 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 724 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |