Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/24376
Title: A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
Authors: Xu, Z 
Keywords: Combinatorial optimization
FPTAS
Machine scheduling
Quadratic knapsack
Strongly polynomial time
Issue Date: 2012
Publisher: Elsevier
Source: European journal of operational research, 2012, v. 218, no. 2, p. 377-381 How to cite?
Journal: European journal of operational research 
Abstract: The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ) for any > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.
URI: http://hdl.handle.net/10397/24376
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2011.10.049
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

12
Last Week
0
Last month
0
Citations as of Apr 12, 2018

WEB OF SCIENCETM
Citations

11
Last Week
0
Last month
2
Citations as of Apr 18, 2018

Page view(s)

63
Last Week
5
Last month
Citations as of Apr 16, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.