ANR project ADDS

Algorithms for Multi-Dimensional Data via Sketches.



Massive geometric data is increasingly common thanks to the proliferation of ubiquitous data-collecting devices, presenting vexing challenges for algorithmic processing. Our approach to deal with this amount of data is to, given an approximation parameter eps, construct a small-sized sketch S of the input data, then solve the problem on S, and finally extend this solution to a (1+eps)-approximation to the original problem. Our research is divided into three parts, requiring expertise in statistics, computational geometry, learning, combinatorics, and algorithms. First, we consider the combinatorial properties of geometric data that are relevant to build compact sketches. Second, we consider the time and space complexities of constructing accurate sketches of data in high dimensions, based on the combinatorial and geometric understanding. Finally, we show how to use the small sketches in order to improve the accuracy and running time of optimization algorithms.



Team





Post-doctorants



Doctorants

Funded: Associated:

Internships





Scientific Visits and Collaborations.



Meetings, Workshops



Invited Talks, Mini-courses



Software

  1. Subgraph Partitioning: Shadoks approach to minimum partition into plane subgraphs.

  2. Motion Planning: Shadoks approach to low-makespan coordinated motion planning.

  3. Low-Crossing Matchings: Matchings with low crossing numbers.

  4. poLYG: Polygon area minimization and maximization.



Publications (HAL pour les publications sous ADDS)


    All related publications need to mention the support from the project as follows:
    Supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).

    Manuscripts

  1. Faster Algorithms for Discrepancy via Lovett-Meka Technique. (Victor Emmanuel-Brunel, Alexandre Louvet, Nabil Mustafa).
    2023.
  2. Robustness of Matchings via Sparse Random Sampling. (Monika Csikos, Nabil Mustafa).
    2023.

    2023

  3. Economical Convex Coverings and Applications (Sunil Arya, Guilherme D. da Fonseca, David M. Mount).
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.
  4. Complexity Results on Untangling Red-Blue Matchings (Arun Kumar Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier).
    EuroCG 2022 special issue of Computational Geometry: Theory and Applications, 2023.
  5. On the Longest Flip Sequence to Untangle Segments in the Plane (Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier).
    International Conference and Workshops on Algorithms and Computation (WALCOM), 2023.

    2022

  6. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes (Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, David M. Mount).
    SODA 2020 special issue of ACM Transactions on Algorithms, 2022.
  7. Complexity Results on Untangling Red-Blue Matchings. (Arun Das, Sandip Das, Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier).
    Proc. of the 15th Latin American Theoretical Informatics Symposium (LATIN), 2022.
  8. Shadoks Approach to Low-Makespan Coordinated Motion Planning. (Loďc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso).
    ACM Journal of Experimental Algorithmics, 2022.
  9. Greedy and Local Search Heuristics to Build Area-Optimal Polygons. (Loďc Crombez, Guilherme D. da Fonseca, Yan Gerard).
    ACM Journal of Experimental Algorithmics, 2022.
  10. Shadoks Approach to Minimum Partition into Plane Subgraphs. (Loďc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo).
    Proc. of the 38th ACM Symposium on Computational Geometry (SoCG '22), 2022.
  11. A Tight Analysis of Geometric Local Search. (Bruno Jartoux, Nabil H. Mustafa).
    Discrete & Computational Geometry (DCG), 2022.
  12. Optimal Approximations Made Easy. (Monika Csikos, Nabil H. Mustafa).
    Information Processing Letters (IPL), 2022.

    2021

  13. Maximizing Covered Area in a Euclidean Plane with Connectivity Constraint. (Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph Mitchell, Nabil H. Mustafa).
    Theory of Computing (TOC), 2021.
  14. Shadoks Approach to Low-Makespan Coordinated Motion Planning. (Loďc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso).
    Proc. of the 37th ACM Symposium on Computational Geometry (SoCG '21), 2021.
  15. Escaping the Curse of Spatial Partitioning: Matchings With Low Crossing Numbers and Their Applications. (Monika Csikos, Nabil H. Mustafa).
    Proc. of the 37th ACM Symposium on Computational Geometry (SoCG '21), 2021.
  16. Tverberg Theorems over Discrete Sets of Points. (Jesús A. De Loera, Thomas Hogan, Frédéric Meunier, Nabil H. Mustafa).
    Book chapter in Contemporary Mathematics: Polytopes and Discrete Geometry, AMS, 2021.

    2020

  17. Optimal Bound on the Combinatorial Complexity of Approximating Polytopes. (Rahul Arya, Sunil Arya, Guilherme D. da Fonseca, David Mount).
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
  18. Efficient Algorithms for Battleship. (Loic Crombez, Guilherme D. da Fonseca, Yan Gerard).
    International Conference on Fun with Algorithms (FUN), 2020.
  19. An Application of the Universality Theorem for Tverberg Partitions to Data Depth and Hitting Convex Sets. (Imre Barany, Nabil H. Mustafa).
    Computational Geometry: Theory and Applications, 2020.