کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903500 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Inapproximability Ratios for Crossing Number
ترجمه فارسی عنوان
نسبت ناپذیری برای عبور از شماره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره گذر پیچیدگی محاسباتی، تقریبی غیر قابل تصور بودن
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Assuming Pâ NP, we show that if there is a constant-factor polynomial c-approximation algorithm for Crossing Number, then câ¥2â1617â1.058824. Adding the Unique Games Conjecture to the hypotheses, then câ¥2âαâ1.121433, where α is the approximation ratio of the algorithm for Maximum Cut by Goemans and Williamson.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 117-122
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 117-122
نویسندگان
Rafael Veiga Pocai,