کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874746 1441191 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Time-approximation trade-offs for inapproximable problems
ترجمه فارسی عنوان
تعاریف تقریبی زمان برای مشکلات غیر قابل پیش بینی
کلمات کلیدی
الگوریتم های تقریبی، الگوریتم های نمایشی، الگوریتم های زیر معادله، سختی تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any r(n), a simple, known scheme gives an approximation ratio of r in time roughly rn/r. We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r-approximation in time 2n/r. We match this with a similarly tight result. We also give a log⁡r-approximation for Min ATSP in time 2n/r and an r-approximation for Max Grundy Coloring in time rn/r. Finally, we investigate the approximability of Min Set Cover, when measuring the running time as a function of the number of sets in the input.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 92, March 2018, Pages 171-180
نویسندگان
, , ,