 A strongly polynomial FPTAS for the symmetric quadratic knapsack problemZhou Xu European Journal of Operational Research, 2012, vol. 218, issue 2, 377-381 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. Keywords: Combinatorial optimization; Quadratic knapsack; FPTAS; Strongly polynomial time; Machine scheduling (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:218:y:2012:i:2:p:377-381 DOI: 10.1016/j.ejor.2011.10.049 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.