کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10225740 1701208 2019 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximability and hardness of geometric hitting set with axis-parallel rectangles
ترجمه فارسی عنوان
تقریب پذیری و سختی قرار گرفتن هندسی با مستطیل های موازی محور
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,