Packing and Covering with Non-Piercing Regions

Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, Saurabh Ray

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). Earlier, PTASs were known only in the setting where the regions were disks. These techniques relied heavily on the circularity of the disks. We develop new techniques to show that a simple local search algorithm yields a PTAS for the problems on non-piercing regions. We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are k-admissible regions (pseudodisks are 2-admissible), and the capacities are bounded by some constant. Our result settles a conjecture of Har-Peled from 2014 in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane. Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity. This extends a result of Ene et al. from 2012.

Original languageEnglish (US)
Pages (from-to)471-492
Number of pages22
JournalDiscrete and Computational Geometry
Volume60
Issue number2
DOIs
StatePublished - Sep 1 2018

Keywords

  • Approximation algorithms
  • Capacitated packing
  • Dominating set
  • Local search
  • Set cover

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Packing and Covering with Non-Piercing Regions'. Together they form a unique fingerprint.

Cite this