کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421215 684163 2012 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation algorithms for a geometric set cover problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximation algorithms for a geometric set cover problem
چکیده انگلیسی

Given a finite set of straight line segments SS in R2R2 and some k∈Nk∈N, is there a subset VV of points on segments in SS with |V|≤k|V|≤k such that each segment of SS contains at least one point in VV? This is a special case of the set covering problem where the family of subsets given can be taken as a set of intersections of the straight line segments in SS. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet we have shown that the problem is still strongly NP-complete [5]. In light of this result, we studied the accuracy of two polynomial-time approximation algorithms along with a third heuristic based algorithm which return segment coverings. We obtain certain theoretical results, and in particular we show that the performance ratio for each of these algorithms is unbounded, in general. Despite this, our experimental results suggest that the cases where this ratio exceeds 2 are rare for “reasonable” methods of placing segments. This is evidence that these polynomial-time algorithms solve the problem accurately in practice.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 1039–1052
نویسندگان
, , , ,