摘要：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 (ð'Y, P), where ð'Y 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.
