| A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM |
| |
| 引用本文： | 吴士泉. A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM[J]. 应用数学学报(英文版), 1994, 10(3): 302-314. DOI: 10.1007/BF02006860 |
| |
| 作者姓名： | 吴士泉 |
| |
| 作者单位： | Institute of Applied Mathematics，the Chinese Academy of Sciences，Beijing 100080，China |
| |
| 摘 要： | ＡＢＲＡＮＣＨＢＯＵＮＤＭＥＴＨＯＤＦＯＲＳＵＢＳＥＴＳＵＭＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（吴士泉）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃ...
|
| 收稿时间： | 1991-01-26 |
A branch bound method for subset sum problem |
| |
| Shiquan Wu. A branch bound method for subset sum problem[J]. Acta Mathematicae Applicatae Sinica, 1994, 10(3): 302-314. DOI: 10.1007/BF02006860 |
| |
| Authors: | Shiquan Wu |
| |
| Affiliation: | (1) Institute of Applied Mathematics, the Chinese Academy of Sciences, 100080 Beijing, China |
| |
| Abstract: | This paper indicates the possible difficulties for applying the interior point method to NPcomplete problems,transforms an NP-complete problem into a nonconvex quadratic program and then develops some convexity theories for it. Lastly it proposes an algorithm which uses Karmarkar's algorithm as a subroutine. The finite convergence of this algorithm is also proved. |
| |
| Keywords: | Subset sum problem nonconvex quadratic program convex envelope interior point method |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
