最悪性能比が2.7834二次元調和算法の提案と評価

• Item type: SIG Technical Reports(1)
• 公開日: 2001-09-25
• タイトル: 最悪性能比が2.7834二次元調和算法の提案と評価
• タイトル / 言語: en
• タイトル: A Two-Dimensional Harmonic Algorithm with Performance Ratio 2.7834
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学／大連理工大学
• 著者所属: 広島大学
• 著者所属: 大連理工大学
• 著者所属(英): en
• 著者所属(英): Hiroshima University,Japan/Dalian University of Technology, The Peoples Republic of China
• 著者所属(英): en
• 著者所属(英): Hiroshima University, Japan
• 著者所属(英): en
• 著者所属(英): Dalian University of Technology, The Peoples Republic of China
• 著者名: HanXin; 藤田, 聡; 郭禾
• 著者名(英): Xin, Han; Satoshi, Fujita; He, Guo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 箱詰め問題は 組み合わせ最適化問題における基本的な問題の１つである。60 70年代から、ずっと 注目され、たくさんの結果が出た.本論では、二次元の箱詰め問題について考察する。以下では 二次元調和算法の改良版であるRTDHを 提案し、その性能を理論的に評価する。評価の結果、提案アルゴリズムの最悪性能比が 2.7834以下であることが示される。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we study an on-line version of the two-dimensional bin packing problem that is the problem of packing a list of rectangular items into a minimum number of unit-square bins in an on-line manner. An on-line algorithm RTDH (Refined Two Dimensional HARMONIC)is proposed and analyzed. We show that RTDH can achieve an asymptotic worst case ratio of less than 2.7834,that beats the best known bound 2.85958.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 93(2001-AL-080), p. 43-50, 発行日 2001-09-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会