کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950814 | 1441036 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An FPTAS for the parametric knapsack problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present a fully polynomial-time approximation scheme (FPTAS) for the problem that, for any desired precision εâ(0,1), computes (1âε)-approximate solutions for all values of the parameter. This is the first FPTAS for the parametric knapsack problem that does not require the slopes and intercepts of the affine functions to be non-negative but works for arbitrary integral values. Our FPTAS outputs O(n2ε) knapsack solutions and runs in strongly polynomial-time O(n2εâ
A(n,ε)), where A(n,ε) denotes the running time of any FPTAS for the traditional (non-parametric) knapsack problem. Even for the special case of positive input data, this is the first FPTAS with a strongly polynomial running time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 126, October 2017, Pages 43-47
Journal: Information Processing Letters - Volume 126, October 2017, Pages 43-47
نویسندگان
Michael Holzhauser, Sven O. Krumke,