TY - GEN
T1 - Improved approximation algorithm for set multicover with non-piercing regions
AU - Raman, Rajiv
AU - Ray, Saurabh
N1 - Publisher Copyright:
© Rajiv Raman and Saurabh Ray.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/8/1
Y1 - 2020/8/1
N2 - 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 S0 of S such that each point is covered by at least d(x) sets from S0. 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.
AB - 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 S0 of S such that each point is covered by at least d(x) sets from S0. 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.
KW - Approximation algorithms
KW - Covering
KW - Geometry
UR - http://www.scopus.com/inward/record.url?scp=85092506399&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092506399&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2020.78
DO - 10.4230/LIPIcs.ESA.2020.78
M3 - Conference contribution
AN - SCOPUS:85092506399
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 28th Annual European Symposium on Algorithms, ESA 2020
A2 - Grandoni, Fabrizio
A2 - Herman, Grzegorz
A2 - Sanders, Peter
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 28th Annual European Symposium on Algorithms, ESA 2020
Y2 - 7 September 2020 through 9 September 2020
ER -