Résumé | Most of the known optimization algorithms need to explore, mark, modify, etc. the instance given as input before producing their results. To do that, the instance is entirely loaded into the memory of the computer and is manipulated by the algorithm. Often, "extra" data structures are also necessary to memorize parameters useful all along the computation or to update the current solution that will be returned as the final product of the program. However, this classical model is no more adapted for many new computing applications. Indeed, nowadays, many fields such as biology, meteorology, finance, etc. produce very large amount of data.
In our works, we have focused on the Vertex Cover problem on huge graphs: in the intrinsic NP-completeness is added the difficulty to manipulate graphs with severe constraints (mainly related to the low memory capacities). We defined a treatment model combining some properties of several existing models in the literature: streaming, online, I/O-efficient, etc. We initially considered three approximation algorithms, which are memory-efficient (they use a memory space in O(log n) bits). We analyzed their performance in terms of solution quality and complexity, in mean and worst cases. We then focused on algorithms that use memory space of n bits. We showed that it could be very worst with strictly less than n bits memory space. Subsequently, we conducted experiments on very large graphs (in the order of billions of vertices and edges). This study showed that in practice, memory-efficient algorithms are better suited to handle large graphs.
This is joint work with Eric Angel (IBISC, Univ. Évry) and Christian Laforest (LIMOS, ISIMA, Clermont-Ferrand). |