کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949466 | 1440190 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Robust recoverable and two-stage selection problems
ترجمه فارسی عنوان
مشکلات سخت افزاری قابل بازیابی و دو مرحله ای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی قوی، پیچیدگی محاسباتی، الگوریتم های تقریبی، مشکل انتخاب
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0-1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O(n)-time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 233, 31 December 2017, Pages 52-64
Journal: Discrete Applied Mathematics - Volume 233, 31 December 2017, Pages 52-64
نویسندگان
Adam Kasperski, PaweÅ ZieliÅski,