Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
Rajiv Raman, Saurabh Ray ยท DROPS (Schloss Dagstuhl โ Leibniz Center for Informatics) ยท 2020
In the Set Multicover problem, we are given a set system (X,๐ฎ), where X is a finite ground set, and ๐ฎ is a collection of subsets of X. Each element x โ X has a non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection ๐ฎ' of ๐ฎ such that each point is covered by at least d(x) sets from ๐ฎ'. In this paper, we study the set multicover problem for set systems defined by points and non-piercing regions in the plane, which includes disks, pseudodisks, k-admissible regions, squares, unit height rectangles, homothets of convex sets, upward paths on a tree, etc. We give a polynomial time (2+ฮต)-approximation algorithm for the set multicover problem (P, โ), where P is a set of points with demands, and โ is a set of non-piercing regions, as well as for the set multicover problem (๐, P), where ๐ is a set of pseudodisks with demands, and P is a set of points in the plane, which is the hitting set problem with demands.