کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225740 | 1701208 | 2019 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximability and hardness of geometric hitting set with axis-parallel rectangles
ترجمه فارسی عنوان
تقریب پذیری و سختی قرار گرفتن هندسی با مستطیل های موازی محور
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Further, we give a polynomial time approximation scheme (PTAS) for the weighted hitting set problem with axis-parallel rectangles when all rectangles have integer side lengths bounded by a constant C. Finally, we show that the problem is NP-hard for rectangles of size 1Ã2 and 2Ã1 even when every rectangle intersects a given unit height horizontal strip.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 141, January 2019, Pages 9-15
Journal: Information Processing Letters - Volume 141, January 2019, Pages 9-15
نویسندگان
Raghunath Reddy Madireddy, Apurva Mudgal,