| 装箱问题的一种新的近似算法 |
| |
| 引用本文： | 孙春玲,陈智斌,李建平.装箱问题的一种新的近似算法[J].云南大学学报(自然科学版),2004,26(5):392-396. |
| |
| 作者姓名： | 孙春玲 陈智斌 李建平 |
| |
| 作者单位： | 云南大学,数学系,云南,昆明,650091 |
| |
| 基金项目： | 国家自然科学研究基金资助项目 ( 10 2 7110 3 )，云南省自然科学研究基金资助项目 ( 2 0 0 3F0 0 15M ) . |
| |
| 摘 要： | 研究了一维装箱问题(Bin Packing Problem),给出了一个新的近似算法:交叉装填算法(简称CF算法).证明了CF算法达到装箱问题的最好的近似值3/2;并且当这些物件的大小按非增性质预先排序后,CF算法的时间复杂度是线性的.
|
| 关 键 词： | 一维装箱问题 NP-完备 近似算法 |
| 文章编号： | 0258-7971(2004)05-0392-05 |
| 修稿时间： | 2003年12月24 |
A new approximation algorithm for Bin-Packing problem |
| |
| SUN Chun-ling,CHEN Zhi-bin,LI Jian-ping.A new approximation algorithm for Bin-Packing problem[J].Journal of Yunnan University(Natural Sciences),2004,26(5):392-396. |
| |
| Authors: | SUN Chun-ling CHEN Zhi-bin LI Jian-ping |
| |
| Institution: | Department of Mathematics, Yunnan University, Kunming 650091, China |
| |
| Abstract: | The Bin-Packing problem is studied again and derived a new32-approximation algorithm in (O(nlogn)) steps;In addition,if the sizes of all objects decreasing according to their sizes,our algorithm runs in O(n) steps. |
| |
| Keywords: | Bin-Packing problem NP-completeness approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《云南大学学报(自然科学版)》下载免费的PDF全文 |
