Kellerer, Hans, Kubzin, Mikhail A. and Strusevich, Vitaly (2005) Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications. Paper (University of Greenwich. Centre for Numerical Modelling and Process Analysis) 05/IM/122 . CMS Press, Greenwich, UK. ISBN 9781904521297

Full text not available from this repository.

Abstract

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

Item Type:	Book
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/884

Actions (login required)

View Item