کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430867 | 688218 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exponential approximation schemata for some network design problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 22, September 2013, Pages 43–52
Journal: Journal of Discrete Algorithms - Volume 22, September 2013, Pages 43–52
نویسندگان
Nicolas Boria, Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos,