کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543722 | 1489579 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An FPTAS for the knapsack problem with parametric weights
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we investigate the parametric weight knapsack problem, in which the item weights are affine functions of the form wi(λ)=ai+λâ
bi for iâ{1,â¦,n} depending on a real-valued parameter λ. The aim is to provide a solution for all values of the parameter. It is well-known that any exact algorithm for the problem may need to output an exponential number of knapsack solutions. We present the first fully polynomial-time approximation schemes (FPTASs) for the problem that, for any desired precision εâ(0,1), compute (1âε)-approximate solutions for all values of the parameter. Among others, we present a strongly polynomial FPTAS running in On5ε2â
log3nεlogn time and a weakly polynomial FPTAS with a running time of On3ε2â
log2n뵉
logPâ
logMlogn, where P is an upper bound on the optimal profit and Mâmax{|W|,nâ
max{|ai|,|bi|:iâ{1,â¦,n}}} for a knapsack with capacity W.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 46, Issue 5, September 2018, Pages 487-491
Journal: Operations Research Letters - Volume 46, Issue 5, September 2018, Pages 487-491
نویسندگان
Nir Halman, Michael Holzhauser, Sven O. Krumke,