دانلود مقاله ISI انگلیسی شماره 109429
ترجمه فارسی عنوان مقاله

تعاریف تقریبی زمان برای مشکلات غیر قابل پیش بینی

عنوان انگلیسی
Time-approximation trade-offs for inapproximable problems
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
109429 2018 10 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Computer and System Sciences, Volume 92, March 2018, Pages 171-180

ترجمه کلمات کلیدی
الگوریتم های تقریبی، الگوریتم های نمایشی، الگوریتم های زیر معادله، سختی تقریبی،
کلمات کلیدی انگلیسی
Approximation algorithms; Exponential algorithms; Sub-exponential algorithms; Hardness of approximation;
پیش نمایش مقاله
پیش نمایش مقاله  تعاریف تقریبی زمان برای مشکلات غیر قابل پیش بینی

چکیده انگلیسی

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.