کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951933 | 1441994 | 2017 | 34 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A general approximation method for bicriteria minimization problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Moreover, we show that our method can be extended to compute an (뱉
(1+2ϵ),αâ
(1+2ϵ))-approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is NP-hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless P=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 1-15
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 1-15
نویسندگان
Pascal Halffmann, Stefan Ruzika, Clemens Thielen, David Willems,