Approximation algorithm for minimum partial multi-cover under a geometric setting
| العنوان: | Approximation algorithm for minimum partial multi-cover under a geometric setting |
|---|---|
| المؤلفون: | Zhao Zhang, Xiaohui Huang, Yingli Ran, Ding-Zhu Du |
| المصدر: | Optimization Letters. 16:667-680 |
| بيانات النشر: | Springer Science and Business Media LLC, 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | 021103 operations research, Control and Optimization, Plane (geometry), 0211 other engineering and technologies, Approximation algorithm, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Combinatorics, Integer, Cover (topology), 0101 mathematics, Element (category theory), Unit (ring theory), Mathematics |
| الوصف: | In a minimum partial set multi-cover problem (MinPSMC), given an element set X, a collection of subsets $${\mathcal {S}} \subseteq 2^X$$ , a cost $$c_S$$ on each set $$S\in {\mathcal {S}}$$ , a covering requirement $$r_x$$ for each element $$x\in X$$ , and an integer k, the goal is to find a sub-collection $${\mathcal {F}} \subseteq {\mathcal {S}}$$ to fully cover at least k elements such that the cost of $${\mathcal {F}}$$ is as small as possible, where element x is fully covered by $${\mathcal {F}}$$ if it belongs to at least $$r_x$$ sets of $${\mathcal {F}}$$ . Recently, it was proved that MinPSMC is at least as hard as the densest k-subgraph problem. The question is: how about the problem in some geometric settings? In this paper, we consider the MinPSMC problem in which X is a set of points on the plane and $${\mathcal {S}}$$ is a set of unit squares (MinPSMC-US). Under the assumption that $$r_x=f_x$$ for every $$x\in X$$ , where $$f_x=|\{S\in {\mathcal {S}}:x\in S\}|$$ is the number of sets containing element x, we design an approximation algorithm achieving approximation ratio $$(1+\varepsilon )$$ for MinPSMC-US. |
| تدمد: | 1862-4480 1862-4472 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::d5c829b92afdde4eb12175e685300df0 https://doi.org/10.1007/s11590-021-01746-9 |
| حقوق: | CLOSED |
| رقم الأكسشن: | edsair.doi...........d5c829b92afdde4eb12175e685300df0 |
| قاعدة البيانات: | OpenAIRE |
Find this article in full text from Springer Verlag. | تدمد: | 18624480 18624472 |
|---|