The symmetric quadratic knapsack problem: approximation and scheduling applications
Kellerer, Hans and Strusevich, Vitaly A. (2012) The symmetric quadratic knapsack problem: approximation and scheduling applications. 4OR: A Quarterly Journal of Operations Research, 10 (2). pp. 111-161. ISSN 1619-4500 (Print), 1614-2411 (Online) (doi:10.1007/s10288-011-0180-x)Full text not available from this repository.
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.
|Additional Information:|| First published online: 27 September 2011.  This research was supported by the EPSRC funded project EP/I018441/1 “Quadratic and Linear Knapsack Problems with Scheduling Applications”.  4OR: A Quarterly Journal of Operations Research is jointly published by the Belgian, French, and Italian Operations Research Societies.|
|Uncontrolled Keywords:||quadratic knapsack, half-product, singlemachine scheduling, FPTAS|
|Subjects:||Q Science > QA Mathematics > QA76 Computer software|
|School / Department / Research Groups:||School of Computing & Mathematical Sciences|
|Last Modified:||12 Dec 2012 16:32|
Actions (login required)