KERNEL (projet région Languedoc-Roussillon), 2012-2015

La génération croissante de grandes masses de données est un phénomème commun à de nombreuses discplines scientifiques (biologie, physique, sciences de l’environnement…) L'exploitation de ces données requière des traitements informatiques systématiques allant du stockage, de la fouille des données à l'optimisation et donc l'algorithmique. Les techniques de pré-traitement sont depuis toujours à la base des méthodes heuristiques. Ce n'est pourtant qu'aux alentours de 2005 que la théorie de la kernelisation offre un cadre formel pour leur étude. Jusqu'ici essentiellement appliquée à des problèmes issus de la théorie des graphes, nous étendrons le champs de la kernelisation à d'autres domaines d'applications à l'interface de l'informatique. Nos objectifs seront aussi de compléter cette théorie du point vue de la complexité algorithmique (bornes, limites).

Le projet compte plusieurs volets. Les trois premiers, complexité, algorithmes et expérimentations, relèvent d'une approche classique de l'informatique. L'étude de la complexité, mesurée ici par la taille des noyaux, a pour objectif d'établir une classification des problèmes. L'algorithmique, ici les règles de réduction, apportent les solutions justifiées mathématiquement aux problèmes étudiés. Enfin les études expérimentales auront un double intérêt la validation des algorithmes proposés ainsi qu'une appréhension plus fine des jeux de données réels permettant éventuellement d'identifier les paramètres structuraux les plus pertinents. Le quatrième volet est de nature plus prospective. Nous tenterons d'établir des ponts entre la kernelisation et la théorie de l'approximabilité. Des liens existent entre l'approximabilité et la complexité paramétré, mais aucun avec la kernelisation. Dans ce projet, nous nous focalisons sur des paramétrisations pour lesquels les problèmes étudiés admettent des algorithmes paramétrés (et donc des noyaux de tailles polynomiales ou exponentielles).

Plus concrètement, les sujets suivants seront au coeur du projet :
- Hiérarchies de paramètres et bornes inférieures
- Règles de réductions et algorithmes génériques de kernelisation
- Amélioration de solutions existantes
- Noyaux et approximations
- Applications et études expérimentales des méthodes de kernelisation