# Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

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

## 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 |