کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476861 1446082 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
چکیده انگلیسی

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.


► We develop a faster fully polynomial time approximation scheme (FPTAS) for the symmetric quadratic knapsack problem.
► The FPTAS is based on a new lower bound and a new upper bound of the optimal objective value.
► The FPTAS runs in strongly polynomial time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 218, Issue 2, 16 April 2012, Pages 377–381
نویسندگان
,