| 箱覆盖问题的半定松驰算法 |
| |
| 引用本文： | 陈峰,姚恩瑜.箱覆盖问题的半定松驰算法[J].运筹学学报,2002,6(2):85-96. |
| |
| 作者姓名： | 陈峰 姚恩瑜 |
| |
| 作者单位： | 浙江大学数学系,杭州,310027 |
| |
| 基金项目： | 国家重点基础研究专项经费资助，国家自然科学基金（19971078）. |
| |
| 摘 要： | 箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。
|
| 关 键 词： | 半定松驰算法 箱覆盖问题 近似算法 组合优化 |
| 修稿时间： | 2001年3月20日 |
Semidefinite Relaxation Algorithm of Bin Covering Problem |
| |
| FENG CHEN ENYU YAO.Semidefinite Relaxation Algorithm of Bin Covering Problem[J].OR Transactions,2002,6(2):85-96. |
| |
| Authors: | FENG CHEN ENYU YAO |
| |
| Abstract: | Bin Covering has been studied in combinatorial optimization and was shown to belong to the class of NP-hard problems. Semidefinite relaxation was successfully employed to solve some combinatorial optimization problems in the last ten years 13]. In the paper, a randomized algorithm based on the technique of semidefinite relaxation for the problem was presented firstly . We prove that the algorithm can performace much better for large scale Bin Covering problems. |
| |
| Keywords: | bin covering problem semidefinite relaxation Approximation algo-rithm combinatorial optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
