ALGOSTRUCT-ID - Algorithmique et structure des problèmes d'identification

Dans le domaine des problèmes d’identification, on se donne une structure discrète (graphe, système d’ensembles, configuration géométrique), qui modélise les données issues d’une application concrète : complexe industriel ou agricole, système d’information, réseau informatique, etc. 

Le but est de sélectionner un petit ensemble d’éléments de la structure, de telle sorte que tous les autres éléments sont identifiés de façon unique par leurs relations aux ensembles sélectionné. Par exemple, dans le cas d’un complexe industriel ou agricole ou d’un réseau informatique, on pourra positionner des capteurs sur des éléments sélectionnés, de telle sorte que tous les emplacements du complexe ou toutes les machines du réseau sont identifiés de façon unique par les capteurs [7].

Les capteurs peuvent être déployés afin de protéger le complexe ou le réseau d’intrusion ou de menaces telles que des incendies.

Ce type de problème est naturel et a été étudié dans divers contextes, sous différents noms dans les dernières décennies, voir par exemple [5, 6].

 Le problème algorithmique correspondant peut être formulé de façon générale comme suit :

 Code Discriminant
Entrée : Un système d’ensembles (X, S), où S est une famille de sous-ensembles d’un ensemble X.
Sortie : Un ensemble C ⊆ X tel que tous les ensembles de S ont une intersection distincte et non-vide avec C.

 Un autre domaine d’application est celui de la fouille de données dans le domaine de l’apprentissage machine [4]. Ainsi, la V-C dimension, introduite par Vapnik et Cervonenkis, est une mesure structurelle des données qui est très utile en apprentissage machine car elle permet de mesurer la complexité des données. Or, la V-C dimension d’un système d’ensembles est directement liée au problème du Code Discriminant, en effet elle mesure la taille maximale d’un code discriminant « idéal » [2].

 D’autres applications du problème concernent par exemple les tests médicaux et les propriétés biologique d’individus [5].

 Des travaux récents soulignent la connexion entre les propriétés structurelles des structures discrètes étudiées et le comportement des problèmes d’identification que nous étudions. C’est le cas pour les classes d’instances qui viennent de systèmes géométriques (par exemple dans le cas des réseaux de capteurs) [7], ou dans le cas des graphes. Dans ce dernier cas, le problème du Code Discriminant est étudié selon diverses déclinaisons telles que les Codes Identifiants ou les Ensembles Localisateurs-Dominants. Ces deux problèmes ont été étudiés pour des familles de graphes structurés qui correspondent à des applications pratiques pertinentes [3].

Pour cette action, nous étudierons ces problèmes d’un point de vue algorithmique et structurel, en lien avec des applications pertinentes et en utilisant notamment les méthodes de l’approche polyhédrale, comme amorcé dans [1].

 Références :

[1] G. Argiroffo, S. Bianchi, Y. Lucarini, A. Wagler. Polyhedra associated with identifying codes in graphs. Discrete Applied Mathematics 245:16–27, 2018.
[2] N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, S. Thomassé. Identifying codes in hereditary classes of graphs and VC-dimension. SIAM Journal on Discrete Mathematics 29(4):2047–2064, 2015.
[3] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Complexity and algorithms. Algorithmica 78(3):914–944, 2017.
[4] S. Goldman, R. Rivest, R. Schapire. Learning binary relations and total orders. SIAM Journal on Computing 22:46–51, 1989.
[5] B. M. E. Moret, H. D. Shapiro. On minimizing a set of tests. SIAM Journal of Scientifical and Statistical Computation 6(4):983–1003, 1985.
[6] A. Rényi. On random generating elements of a finite Boolean algebra. Acta Scientiarum Mathematicarum Szeged 22:75–81, 1961.
[7] R. Ungrangsi, A. Trachtenberg, D. Starobinski. An implementation of indoor location detection systems based on identifying codes. Proc. INTELLCOMM 2004.