The symmetric quadratic knapsack problem: approximation and scheduling applications
Tools
Tools
Tools
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)
Full text not available from this repository.Official URL: http://dx.doi.org/10.1007/s10288-011-0180-x
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.
| Item Type: | Article |
|---|---|
| Additional Information: | [1] First published online: 27 September 2011. [2] This research was supported by the EPSRC funded project EP/I018441/1 “Quadratic and Linear Knapsack Problems with Scheduling Applications”. [3] 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 |
| Related URLs: | |
| Last Modified: | 12 Dec 2012 16:32 |
| URI: | http://gala.gre.ac.uk/id/eprint/9029 |
Actions (login required)
| View Item |