On nonlinear multi-covering problems

Reuven Cohen, Mira Gonen, Asaf Levin, Shmuel Onn

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

1 اقتباس (Scopus)

ملخص

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands { d0, ⋯ , dn - 1} and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly di subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)645-659
عدد الصفحات15
دوريةJournal of Combinatorial Optimization
مستوى الصوت33
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 فبراير 2017

بصمة

أدرس بدقة موضوعات البحث “On nonlinear multi-covering problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا