On combinatorial approximation algorithms in geometry

Abstract : The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results
Complete list of metadatas

Contributor : Abes Star <>
Submitted on : Wednesday, March 13, 2019 - 11:03:06 AM
Last modification on : Tuesday, May 14, 2019 - 9:32:10 AM
Long-term archiving on : Friday, June 14, 2019 - 12:58:00 PM


Version validated by the jury (STAR)


  • HAL Id : tel-02066140, version 1



Bruno Jartoux. On combinatorial approximation algorithms in geometry. Distributed, Parallel, and Cluster Computing [cs.DC]. Université Paris-Est, 2018. English. ⟨NNT : 2018PESC1078⟩. ⟨tel-02066140⟩



Record views


Files downloads