Skip navigation

Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications

Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications

Kellerer, Hans and Strusevich, Vitaly A. (2008) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57 (4). pp. 769-795. ISSN 0178-4617 (Print), 1432-0541 (Online) (doi:10.1007/s00453-008-9248-1)

Full text not available from this repository.

Abstract

We design a fully polynomial-time approximation scheme (FPTAS) for a knapsack problem to minimize a symmetric quadratic function. We demonstrate how the designed FPTAS can be adopted for several single machine scheduling problems to minimize the sum of the weighted completion times. The applications presented in this paper include problems with a single machine non-availability interval (for both the non-resumable and the resumable scenarios) and a problem of planning a single machine maintenance period; the latter problem is closely related to a single machine scheduling problem with two competing agents. The running time of each presented FPTAS is strongly polynomial.

Item Type: Article
Additional Information: [1] Published online: 11 November 2008. [2] The original publication is available at www.springerlink.com.
Uncontrolled Keywords: quadratic knapsack, single machine scheduling, total weighted completion time, availability constraints, scheduling agents, FPTAS
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:
Last Modified: 14 Oct 2016 09:09
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/3605

Actions (login required)

View Item View Item