10 Search Results for "Ray, Saurabh"


Document
On Geometric Priority Set Cover Problems

Authors: Aritra Banik, Rajiv Raman, and Saurabh Ray

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane.

Cite as

Aritra Banik, Rajiv Raman, and Saurabh Ray. On Geometric Priority Set Cover Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.ISAAC.2021.12,
  author =	{Banik, Aritra and Raman, Rajiv and Ray, Saurabh},
  title =	{{On Geometric Priority Set Cover Problems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.12},
  URN =		{urn:nbn:de:0030-drops-154459},
  doi =		{10.4230/LIPIcs.ISAAC.2021.12},
  annote =	{Keywords: Approximation algorithms, geometric set cover, local search, quasi-uniform sampling}
}
Document
Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions

Authors: Rajiv Raman and Saurabh Ray

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


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 non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection 𝒮' 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 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, ℛ), where P is a set of points with demands, and ℛ is a set of non-piercing 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.

Cite as

Rajiv Raman and Saurabh Ray. Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.ESA.2020.78,
  author =	{Raman, Rajiv and Ray, Saurabh},
  title =	{{Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{78:1--78:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.78},
  URN =		{urn:nbn:de:0030-drops-129441},
  doi =		{10.4230/LIPIcs.ESA.2020.78},
  annote =	{Keywords: Approximation algorithms, geometry, Covering}
}
Document
On Geometric Set Cover for Orthants

Authors: Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.

Cite as

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2019.26,
  author =	{Bringmann, Karl and Kisfaludi-Bak, S\'{a}ndor and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{On Geometric Set Cover for Orthants}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.26},
  URN =		{urn:nbn:de:0030-drops-111476},
  doi =		{10.4230/LIPIcs.ESA.2019.26},
  annote =	{Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
Document
Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
In their seminal work, Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010] showed that a wide class of geometric set cover (SC) problems admit a PTAS via local search - this is one of the most general approaches known for such problems. Their result applies if a naturally defined "exchange graph" for two feasible solutions is planar and is based on subdividing this graph via a planar separator theorem due to Frederickson [Greg N. Frederickson, 1987]. Obtaining similar results for the related maximum coverage problem (MC) seems non-trivial due to the hard cardinality constraint. In fact, while Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] have shown (via a different analysis) that local search yields a PTAS for two-dimensional real halfspaces, they only conjectured that the same holds true for dimension three. Interestingly, at this point it was already known that local search provides a PTAS for the corresponding set cover case and this followed directly from the approach of Mustafa and Ray. In this work we provide a way to address the above-mentioned issue. First, we propose a color-balanced version of the planar separator theorem. The resulting subdivision approximates locally in each part the global distribution of the colors. Second, we show how this roughly balanced subdivision can be employed in a more careful analysis to strictly obey the hard cardinality constraint. More specifically, we obtain a PTAS for any "planarizable" instance of MC and thus essentially for all cases where the corresponding SC instance can be tackled via the approach of Mustafa and Ray. As a corollary, we confirm the conjecture of Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding real halfspaces in dimension three. We feel that our ideas could also be helpful in other geometric settings involving a cardinality constraint.

Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ESA.2018.17,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.17},
  URN =		{urn:nbn:de:0030-drops-94809},
  doi =		{10.4230/LIPIcs.ESA.2018.17},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
Document
On a Problem of Danzer

Authors: Nabil H. Mustafa and Saurabh Ray

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
Let C be a bounded convex object in R^d, and P a set of n points lying outside C. Further let c_p, c_q be two integers with 1 <= c_q <= c_p <= n - floor[d/2], such that every c_p + floor[d/2] points of P contains a subset of size c_q + floor[d/2] whose convex-hull is disjoint from C. Then our main theorem states the existence of a partition of P into a small number of subsets, each of whose convex-hull is disjoint from C. Our proof is constructive and implies that such a partition can be computed in polynomial time. In particular, our general theorem implies polynomial bounds for Hadwiger-Debrunner (p, q) numbers for balls in R^d. For example, it follows from our theorem that when p > q >= (1+beta) * d/2 for beta > 0, then any set of balls satisfying the HD(p,q) property can be hit by O(q^2 p^{1+1/(beta)} log p) points. This is the first improvement over a nearly 60-year old exponential bound of roughly O(2^d). Our results also complement the results obtained in a recent work of Keller et al. where, apart from improvements to the bound on HD(p, q) for convex sets in R^d for various ranges of p and q, a polynomial bound is obtained for regions with low union complexity in the plane.

Cite as

Nabil H. Mustafa and Saurabh Ray. On a Problem of Danzer. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 64:1-64:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{mustafa_et_al:LIPIcs.ESA.2018.64,
  author =	{Mustafa, Nabil H. and Ray, Saurabh},
  title =	{{On a Problem of Danzer}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{64:1--64:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.64},
  URN =		{urn:nbn:de:0030-drops-95271},
  doi =		{10.4230/LIPIcs.ESA.2018.64},
  annote =	{Keywords: Convex polytopes, Hadwiger-Debrunner numbers, Epsilon-nets, Balls}
}
Document
Planar Support for Non-piercing Regions and Applications

Authors: Rajiv Raman and Saurabh Ray

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
Given a hypergraph H=(X,S), a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S in S, the sub-graph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraph H_R(B) = (B, {B_r}_{r in R}), where B_r = {b in B: b cap r != empty set} has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R cup B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

Cite as

Rajiv Raman and Saurabh Ray. Planar Support for Non-piercing Regions and Applications. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.ESA.2018.69,
  author =	{Raman, Rajiv and Ray, Saurabh},
  title =	{{Planar Support for Non-piercing Regions and Applications}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.69},
  URN =		{urn:nbn:de:0030-drops-95320},
  doi =		{10.4230/LIPIcs.ESA.2018.69},
  annote =	{Keywords: Geometric optimization, packing and covering, non-piercing regions}
}
Document
Brief Announcement
Brief Announcement: Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
In this announcement, we show that the classical Maximum Coverage problem (MC) admits a PTAS via local search in essentially all cases where the corresponding instances of Set Cover (SC) admit a PTAS via the local search approach by Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010]. As a corollary, we answer an open question by Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding half-spaces in R^3 thereby settling the existence of PTASs for essentially all natural cases of geometric MC problems. As an intermediate result, we show a color-balanced version of the classical planar subdivision theorem by Frederickson [Greg N. Frederickson, 1987]. We believe that some of our ideas may be useful for analyzing local search in other settings involving a hard cardinality constraint.

Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Brief Announcement: Approximation Schemes for Geometric Coverage Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 107:1-107:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ICALP.2018.107,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Brief Announcement: Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{107:1--107:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.107},
  URN =		{urn:nbn:de:0030-drops-91113},
  doi =		{10.4230/LIPIcs.ICALP.2018.107},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
Document
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}
}
Document
Improved Local Search for Geometric Hitting Set

Authors: Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set D of geometric objects, compute the minimum-sized subset of P that hits all objects in D. For the case where D is a set of disks in the plane, a PTAS was finally achieved in 2010, with a surprisingly simple algorithm based on local-search. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. That leaves open the question of whether a better understanding - both combinatorial and algorithmic - of local search and the problem can give a better approximation ratio in a more reasonable time. In this paper, we investigate this question for hitting sets for disks in the plane. We present tight approximation bounds for (3,2)-local search and give an (8+\epsilon)-approximation algorithm with expected running time ˜O(n^{2.34}); the previous-best result achieving a similar approximation ratio gave a 10-approximation in time O(n^{15}) -- that too just for unit disks. The techniques and ideas generalize to (4,3) local search. Furthermore, as mentioned earlier, local-search has been used for several other geometric optimization problems; for all these problems our results show that (3,2) local search gives an 8-approximation and no better \footnote{This is assuming the use of the standard framework. Improvement of the approximation factor by using additional properties specific to the problem may be possible.}. Similarly (4,3)-local search gives a 5-approximation for all these problems.

Cite as

Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Improved Local Search for Geometric Hitting Set. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 184-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bus_et_al:LIPIcs.STACS.2015.184,
  author =	{Bus, Norbert and Garg, Shashwat and Mustafa, Nabil H. and Ray, Saurabh},
  title =	{{Improved Local Search for Geometric Hitting Set}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{184--196},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.184},
  URN =		{urn:nbn:de:0030-drops-49135},
  doi =		{10.4230/LIPIcs.STACS.2015.184},
  annote =	{Keywords: hitting sets, Delaunay triangulation, local search, disks, geometric algorithms}
}
Document
Near-Optimal Generalisations of a Theorem of Macbeath

Authors: Nabil H. Mustafa and Saurabh Ray

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)


Abstract
The existence of Macbeath regions is a classical theorem in convex geometry ("A Theorem on non-homogeneous lattices", Annals of Math, 1952). We refer the reader to the survey of I. Barany for several applications. Recently there have been some striking applications of Macbeath regions in discrete and computational geometry. In this paper, we study Macbeath's problem in a more general setting, and not only for the Lebesgue measure as is the case in the classical theorem. We prove near-optimal generalizations for several basic geometric set systems. The problems and techniques used are closely linked to the study of espilon-nets for geometric set systems.

Cite as

Nabil H. Mustafa and Saurabh Ray. Near-Optimal Generalisations of a Theorem of Macbeath. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 578-589, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{mustafa_et_al:LIPIcs.STACS.2014.578,
  author =	{Mustafa, Nabil H. and Ray, Saurabh},
  title =	{{Near-Optimal Generalisations of a Theorem of Macbeath}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{578--589},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.578},
  URN =		{urn:nbn:de:0030-drops-44890},
  doi =		{10.4230/LIPIcs.STACS.2014.578},
  annote =	{Keywords: Epsilon Nets, Cuttings, Union Complexity, Geometric Set systems, Convex Geometry}
}
  • Refine by Author
  • 7 Ray, Saurabh
  • 4 Raman, Rajiv
  • 3 Mustafa, Nabil H.
  • 2 Chaplick, Steven
  • 2 De, Minati
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 4 Theory of computation → Packing and covering problems
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 4 local search
  • 3 Approximation algorithms
  • 2 Set Cover
  • 2 approximation scheme
  • 2 balanced separators
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 4 2018
  • 1 2014
  • 1 2015
  • 1 2016
  • 1 2019
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail