Search Results

Documents authored by Jartoux, Bruno

Document
DOI: 10.4230/LIPIcs.SoCG.2020.5
The ε-t-Net Problem

Authors: Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study a natural generalization of the classical ε-net problem (Haussler - Welzl 1987), which we call the ε-t-net problem: Given a hypergraph on n vertices and parameters t and ε ≥ t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least ε n contains a set in S. When t=1, this corresponds to the ε-net problem. We prove that any sufficiently large hypergraph with VC-dimension d admits an ε-t-net of size O((1+log t)d/ε log 1/ε). For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of O(1/ε)-sized ε-t-nets. We also present an explicit construction of ε-t-nets (including ε-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of ε-nets (i.e., for t=1), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.
Cite as

Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5,
  author =	{Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena},
  title =	{{The \epsilon-t-Net Problem}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.5},
  URN =		{urn:nbn:de:0030-drops-121639},
  doi =		{10.4230/LIPIcs.SoCG.2020.5},
  annote =	{Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.48
Optimality of Geometric Local Search

Authors: Bruno Jartoux and Nabil H. Mustafa

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Up until a decade ago, the algorithmic status of several basic çlass{NP}-complete problems in geometric combinatorial optimisation was unresolved. This included the existence of polynomial-time approximation schemes (PTASs) for hitting set, set cover, dominating set, independent set, and other problems for some basic geometric objects. These past nine years have seen the resolution of all these problems--interestingly, with the same algorithm: local search. In fact, it was shown that for many of these problems, local search with radius lambda gives a (1+O(lambda^{-1/2}))-approximation with running time n^{O(lambda)}. Setting lambda = Theta(epsilon^{-2}) yields a PTAS with a running time of n^{O(epsilon^{-2})}. On the other hand, hardness results suggest that there do not exist PTASs for these problems with running time poly(n) * f(epsilon) for any arbitrary f. Thus the main question left open in previous work is in improving the exponent of n to o(epsilon^{-2}). We show that in fact the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient, of independent interest, is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results. Our construction extends to other graph families with small separators.
Cite as

Bruno Jartoux and Nabil H. Mustafa. Optimality of Geometric Local Search. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jartoux_et_al:LIPIcs.SoCG.2018.48,
  author =	{Jartoux, Bruno and Mustafa, Nabil H.},
  title =	{{Optimality of Geometric Local Search}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.48},
  URN =		{urn:nbn:de:0030-drops-87615},
  doi =		{10.4230/LIPIcs.SoCG.2018.48},
  annote =	{Keywords: local search, expansion, matchings, Hall's marriage theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.38
Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning

Authors: Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The packing lemma of Haussler states that given a set system (X,R) with bounded VC dimension, if every pair of sets in R have large symmetric difference, then R cannot contain too many sets. Recently it was generalized to the shallow packing lemma, applying to set systems as a function of their shallow-cell complexity. In this paper we present several new results and applications related to packings: * an optimal lower bound for shallow packings, * improved bounds on Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry, * we observe that Mnets provide a general, more powerful framework from which the state-of-the-art unweighted epsilon-net results follow immediately, and * simplifying and generalizing one of the main technical tools in [Fox et al. , J. of the EMS, to appear].
Cite as

Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.SoCG.2017.38,
  author =	{Dutta, Kunal and Ghosh, Arijit and Jartoux, Bruno and Mustafa, Nabil H.},
  title =	{{Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.38},
  URN =		{urn:nbn:de:0030-drops-71991},
  doi =		{10.4230/LIPIcs.SoCG.2017.38},
  annote =	{Keywords: Epsilon-nets, Haussler's packing lemma, Mnets, shallow-cell complexity, shallow packing lemma}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact