Raman, Rajiv ;
Ray, Saurabh
Improved Approximation Algorithm for Set Multicover with NonPiercing Regions
Abstract
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 nonnegative demand d(x). The goal is to pick a smallest cardinality subcollection 𝒮' 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 nonpiercing regions in the plane, which includes disks, pseudodisks, kadmissible 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 nonpiercing 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.
BibTeX  Entry
@InProceedings{raman_et_al:LIPIcs:2020:12944,
author = {Rajiv Raman and Saurabh Ray},
title = {{Improved Approximation Algorithm for Set Multicover with NonPiercing Regions}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {78:178:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12944},
URN = {urn:nbn:de:0030drops129441},
doi = {10.4230/LIPIcs.ESA.2020.78},
annote = {Keywords: Approximation algorithms, geometry, Covering}
}
26.08.2020
Keywords: 

Approximation algorithms, geometry, Covering 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 