| Article ID: | iaor20041793 |
| Country: | China |
| Volume: | 17A |
| Issue: | 4 |
| Start Page Number: | 460 |
| End Page Number: | 470 |
| Publication Date: | Jan 2002 |
| Journal: | Applied Mathematics (A Journal of Chinese Universities) |
| Authors: | Yao Enyu, Chen Feng |
| Keywords: | knapsack problem |
Knapsack is a classical NP-hard problem. In the last ten years, semi-definite relaxation technique has been successfully employed to solve some combinatorial optimization problems. The paper presents the rank one semi-definite relaxation programming (SKSSA) of the knapsack problem. Based on this, a randomized approximation algorithm KSSD to solve a knapsack problem is constructed.