The symmetric quadratic knapsack problem: approximation and scheduling applications |
| |
| Authors: | Hans Kellerer Vitaly A. Strusevich |
| |
| Affiliation: | 1. Institut f??r Statistik und Operations Research, Universit?t Graz, Universit?tsstra?e 15, 8010, Graz, Austria
2. School of Computing and Mathematical Science, University of Greenwich, Park Row, Greenwich, SE10 9LS, London, UK
|
| |
| Abstract: | This paper reviews two problems of Boolean non-linear programming: the Symmetric Quadratic Knapsack Problem and the Half-Product Problem. The problems are related since they have a similar quadratic non-separable objective function. For these problems, we focus on the development of fully polynomial-time approximation schemes, especially of those with strongly polynomial time, and on their applications to various scheduling problems. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
