## Abstract

In the Set Multicover problem, we are given a set system (X, S) , where X is a finite ground set, and S 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 S^{′} of S such that each point is covered by at least d(x) sets from S^{′}. 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, R) , where P is a set of points with demands, and R is a set of non-piercing regions, as well as for the set multicover problem (D, P) , where D 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.

Original language | English (US) |
---|---|

Pages (from-to) | 566-591 |

Number of pages | 26 |

Journal | Discrete and Computational Geometry |

Volume | 68 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2022 |

## Keywords

- Geometric hypergraphs
- Local search
- Packing and covering
- Planar support
- Pseudodisks

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics