Satisfaction de Contraintes - Grenoble, France - Université Grenoble Alpes

Université Grenoble Alpes

Entreprise vérifiée

Grenoble, France

il y a 1 semaine

Posté par:

Sophie Dupont

beBee Recruiter

Description

**Satisfaction de contraintes : Algorithmes et complexité // Constraint Satisfaction : Algorithms and Complexity**:

- Réf **ABG-123816**
**ADUM-57118**
- Sujet de Thèse- 14/05/2024- Université Grenoble Alpes- Lieu de travail- GRENOBLE Cedex 1 - France- Intitulé du sujet- Satisfaction de contraintes : Algorithmes et complexité // Constraint Satisfaction : Algorithms and Complexity- Mots clés- CSP, Reconfiguration, Approximation, Algorithmes
- CSP, Reconfiguration, Approximation, Algorithms**Description du sujet**:

- Le Problème de Satisfaction de Contraintes (CSP en anglais) est un problème classique en informatique, dont la complexité a été très étudiée depuis son introduction. Dans une percée récente, Zhuk et Bulatov ont obtenu (de manière indépendante) une classification complète de la complexité des CSP. Avec ce résultat comme point de départ, ainsi qu'une simplification très récente de Zhuk, notre objectif est une meilleure compréhension de la complexité de variantes de ce problème liées à l'optimisation, la robustesse, et la reconfiguration. Pour ce faire, nous souhaitons étendre à ces variantes les techniques algébriques et topologiques qui ont été développé avec succès pour le CSP original, dans le but d'obtenir des algorithmes efficaces (exact ou approchés), ainsi qu'une caractérisation fine des instances traitables.
The Constraint Satisfaction Problem (CSP) is a classical problem in Theoretical Computer Science, whose complexity has been studied intensively since the very beginning of the field. In a recent breakthrough, Zhuk and Bulatov obtained (independently) a complete classification of the complexity of the CSP. With this result as a starting point, as well as a very recent simplification by
- Zhuk, our goal is to obtain a better understanding of the complexity of variations of this problem related to optimization, robustness, and reconfiguration. For this purpose, we would like to extend algebraic and topological techniques that have been developed for the CSP to these settings, in order to obtain polynomial-time exact and approximation algorithms, as well as structural characterizations of tractable instances.
Début de la thèse : 01/10/2024**Nature du financement**:
**Précisions sur le financement**:

- Concours allocations**Présentation établissement et labo d'accueil**:

- Université Grenoble Alpes**Etablissement délivrant le doctorat**:

- Université Grenoble Alpes**Ecole doctorale**:

- 217 MSTII - Mathématiques, Sciences et technologies de l'information, Informatique- Etudiants ayant un M2 en informatique théorique ou mathématiques, avec des connaissances en algorithmique, complexité, graphes, optimisation combinatoire.
- M2 students in theoretical computer science or mathematics, with a background in algorithms, complexity graphs, combinatorial optimization.-
- 09/06/2024