Improved approximation algorithm for set multicover with non-piercing regions

Rajiv Raman, Saurabh Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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.

Original languageEnglish (US)
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771627
DOIs
StatePublished - Aug 1 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume173
ISSN (Print)1868-8969

Conference

Conference28th Annual European Symposium on Algorithms, ESA 2020
CountryItaly
CityVirtual, Pisa
Period9/7/209/9/20

Keywords

  • Approximation algorithms
  • Covering
  • Geometry

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Improved approximation algorithm for set multicover with non-piercing regions'. Together they form a unique fingerprint.

Cite this