Kellerer, Hans and Strusevich, Vitaly A. (2011) 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:https://doi.org/10.1007/s10288-011-0180-x)

Full text not available from this repository.

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] This research was supported by the EPSRC funded project EP/I018441/1 “Quadratic and Linear Knapsack Problems with Scheduling Applications”. [2] 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
Faculty / School / Research Centre / Research Group:	Faculty of Liberal Arts & Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:22
URI:	http://gala.gre.ac.uk/id/eprint/9029

Actions (login required)

View Item