کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950901 1441042 2017 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation schemes for the parametric knapsack problem
ترجمه فارسی عنوان
طرح تقریبی برای مشکل پارامتریک قیچی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We provide the first (parametric) polynomial time approximation scheme (PTAS) for the parametric 0-1 knapsack problem. Moreover, we exploit the connection between the parametric problem and the bicriteria problem in order to show that the parametric 0-1 knapsack problem admits a parametric FPTAS when the parameter is restricted to the positive real line and the slopes and intercepts of the affine-linear profit functions of the items are nonnegative. The method used to obtain this result applies to many linear parametric optimization problems and provides a general connection between bicriteria and linear parametric optimization problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 120, April 2017, Pages 11-15
نویسندگان
, , , ,