کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434943 | 1441655 | 2015 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate by thinning: Deriving fully polynomial-time approximation schemes
ترجمه فارسی عنوان
تقریبا با نازک شدن: طرح های تقریبی به طور کامل چندجمله ای را در بر می گیرد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های تقریبی، مشتق برنامه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The fully polynomial-time approximation scheme (FPTAS) is a class of approximation algorithms for optimisation problems that is able to deliver an approximate solution within any chosen ratio in polynomial time. By generalising Bird and de Moor's Thinning Theorem to a property between three orderings, we come up with a datatype-generic strategy for constructing fold-based FPTASs. Greedy, thinning, and approximation algorithms can thus be seen as a series of generalisations. Components needed in constructing an FPTAS are often natural extensions of those in the thinning algorithm. Design of complex FPTASs is thus made easier, and some of the resulting algorithms turn out to be simpler than those in previous works.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Science of Computer Programming - Volume 98, Part 4, 1 February 2015, Pages 484–515
Journal: Science of Computer Programming - Volume 98, Part 4, 1 February 2015, Pages 484–515
نویسندگان
Shin-Cheng Mu, Yu-Han Lyu, Akimasa Morihata,