| 一维装箱问题的交叉算法分析 |
| |
| 引用本文： | 李杉林.一维装箱问题的交叉算法分析[J].台州学院学报,2009,31(3):1-5. |
| |
| 作者姓名： | 李杉林 |
| |
| 作者单位： | 台州学院,数学与信息工程学院,浙江,临海,317000 |
| |
| 摘 要： | 2004年孙春玲等研究了一维装箱问题,给出了一个近似程度最好的近似值为3/2的近似算法-交叉算法.遗憾的是他们的交叉算法的近似值分析是错误的,本文通过两个反例说明了他们的错误所在,并给出一个正确的近似值分析.
|
| 关 键 词： | 装箱问题 强NP-难 近似算法 反例 |
An Analysis of Cross Fit Algorithm for Bin Parking Problem |
| |
| LI Shan-Lin.An Analysis of Cross Fit Algorithm for Bin Parking Problem[J].Journal of Taizhou University,2009,31(3):1-5. |
| |
| Authors: | LI Shan-Lin |
| |
| Institution: | LI Shan-Lin (School of Mathematics and Information Engineering, Taizhou University, Linhai 317000, China) |
| |
| Abstract: | In 2004, Sun Chun-ling, et al. studied the Bin-Packing problem and proposed an approximation algorithm called Cross Fit algorithm. Its worst-case performance ratio bound is 3/2 which is the best bound of heuristics for the Bin-Packing problem. The purpose of this paper is to point out that their analysis of the bound for Cross Fit algorithm is incorrect by two counterexamples and then provide a correct analysis. |
| |
| Keywords: | Bin-Packing problem strongly NP＇hard approximation algorithm counterexample |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
