1 Search Results for "Govindarajan, Sathish"

Document

DOI: 10.4230/LIPIcs.ESA.2016.47

Packing and Covering with Non-Piercing Regions

Authors: Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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). We show that the local search algorithm that yields PTASs when the regions are disks [Aschner/Katz/Morgenstern/Yuditsky, WALCOM 2013; Gibson/Pirwani, 2005; Mustafa/Raman/Ray, 2015] can be extended to work for non-piercing regions. While such an extension is intuitive and natural, attempts to settle this question have failed even for pseudodisks. The techniques used for analysis when the regions are disks rely heavily on the underlying geometry, and do not extend to topologically defined settings such as pseudodisks. In order to prove our results, we introduce novel techniques that we believe will find applications in other problems. 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. Our result settles a conjecture of Har-Peled (see Conclusion of [Har-Peled, SoCG 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, extending one of the results of Ene et al. [Ene/Har-Peled/Raichel, SoCG 2012].

Cite as

Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and Covering with Non-Piercing Regions. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{govindarajan_et_al:LIPIcs.ESA.2016.47,
  author =	{Govindarajan, Sathish and Raman, Rajiv and Ray, Saurabh and Basu Roy, Aniket},
  title =	{{Packing and Covering with Non-Piercing Regions}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.47},
  URN =		{urn:nbn:de:0030-drops-63591},
  doi =		{10.4230/LIPIcs.ESA.2016.47},
  annote =	{Keywords: Local Search, Set Cover, Dominating Set, Capacitated Packing, Approximation algorithms}
}

Refine by Author
1 Basu Roy, Aniket
1 Govindarajan, Sathish
1 Raman, Rajiv
1 Ray, Saurabh

Refine by Classification

Refine by Keyword
1 Approximation algorithms
1 Capacitated Packing
1 Dominating Set
1 Local Search
1 Set Cover

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Govindarajan, Sathish"

Packing and Covering with Non-Piercing Regions

Abstract

Cite as

Thanks for your feedback!

Could not send message