DS0705 - Fondements du numérique

Structural geometric approximation for algorithms – SAGA

Submission summary

Combinatorial optimization arises naturally in a variety of resource management problems in public transportation companies, industrial manufacturing, financial and health-care institutions. Standing out are two categories of optimization problems, packing and covering, with applications in material and manpower planning, scheduling, routing, investment and resource allocation. The sad fact is that these problems are not only NP-hard, but also provably hard to approximate: for instance, no algorithm can approximate set-cover within a logarithmic multiplicative factor or independent set within a polynomial multiplicative factor. Even worse, with the proliferation of ubiquitous data-collecting devices and fast distributed data-sharing capabilities, the inputs to these problems are so large and complex that traditional computational ideas are infeasible. The task of finding efficient, reliable (provably good) and flexible solutions to packing and covering problems remains a challenge with high potential impact.

One key to avoiding the inherent NP-hardness of these combinatorial problems is to take into account the geometric structure of data that exists in many applications. Such structures, however, become very large with data increases (which, e.g., for business data doubles worldwide every 1.2 years). This dismal state of affairs in theory then translates current applications still using heuristics with the hope (and no guarantees) that they would run fast and produce good-quality solutions. Recent effective approaches to large computational problems therefore rely on structures which are provably small; hence the field of streaming algorithms computes small `sketches' of data, or sub-linear algorithms that even avoid looking at the entire data using structures called epsilon-nets. The core of both these approaches is to show that the structural essence of the entire data can be captured by a small-sized subset. Closer to our theme, the key to the resolution of a long-standing open problem on minimum set-cover for disks was another small-sized structure, namely geometric separators.

The goal of this project is the design of provably efficient and reliable algorithms for packing and covering problems through the study of small-sized structural approximations of geometric data. This involves the analysis of geometric data (e.g., epsilon-nets) to construct small-sized geometric structures (e.g., separators) to design efficient algorithms for packing and covering problems for reliable software solution. A successful completion of this proposal would entail: new structural understanding of geometric data; leading directly to better algorithms for problems on geometric data; careful implementation and algorithmic fine-tuning; solving instances of specific problems of relevance to industry; and finally integration into the state-of-the-art libraries and technologies.

The lead investigator of this `jeune chercheur' proposal, Nabil Mustafa, has an expertise in delivering geometric tools to application areas, both in academic and industrial settings. This expertise is complemented by an expert in algorithms for combinatorial optimization problems (Claire Mathieu), an expert in geometric structures (Xavier Goaoc), and experts with strong experience in use of optimization (Frederic Meunier) and geometry (Lilian Buzer) in industry.

This project builds on a dynamic that has developed (centered at Marne-la-Vallee) with recent arrivals in greater Paris of Nabil Mustafa and Claire Mathieu in 2012, and Xavier Goaoc in 2013. Formed through discussions where we realized the many relations between our different areas, this proposal stands at the cross-roads of algorithms, geometry and optimization.

Project coordination

Nabil Hassan Mustafa (Laboratoire Informatique Gaspard Monge (LIGM))

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LGIM - CCIR-IDF ESIEE Paris Laboratoire Informatique Gaspard Monge (LIGM)

Help of the ANR 183,040 euros
Beginning and duration of the scientific project: September 2014 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter