Défiler vers le haut

Licence Creative Commons Vangelis Th. Paschos : Sparsification et approximation sous-exponentielle

24 février 2017
Durée : 00:52:47
Nombre de vues 189
Nombre d’ajouts dans une liste de lecture 1
Nombre de favoris 0

Le concept de la « sparsification des instances » est un outil bien connu dans le paradigme du calcul exact étant donné que cette notion est très fortement liée à l’Hypothèse du Temps Exponentiel (Exponential Time Hypothesis). Dans cette présentation, nous décrivons quelques premiers pas qui tentent d’étendre la notion de sparsification dans le but d’en faire un outil pour l’approximation sous-exponentielle. Plus spécifiquement, nous décrivons un nouvel outil pour l’inapproximabilité sous-exponentielle, la « sparsification qui préserve l’approximabilité » et montrons comment on peut utiliser cet outil afin d’obtenir les résultats d’inapproximabilité exponentielle pour des problèmes fondamentaux d’optimisation combinatoire tels l’ensemble dominant minimum, la couverture minimum d’ensembles, etc.

Vangelis Paschos is Professor of Computer Science in the University Paris-Dauphine and member of the reseach lab LAMSADE. He is currently working on Complexity Theory, Efficient Approximation of Hard Problems and Combinatorial Optimization. Professor Paschos published more then 100 articles in top international j ournals. He is a member in the editorial board of Theoretical Computer Science, European Journal of Operational Research, RAIRO - Operations Research, among others. He is senior member of the "Institut Universitaire de France".

 Informations