2026-07-23T00:26:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12944 2024-03-06T10:51:09Z ddc:004 open_access

Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions Raman, Rajiv Ray, Saurabh Approximation algorithms geometry Covering 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajiv Raman and Saurabh Ray 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.78 urn:nbn:de:0030-drops-129441 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.78 eng https://creativecommons.org/licenses/by/3.0/legalcode