Offre de th
Forum 'Emplois' - Sujet créé le 2014-05-06 par Vincent Tkindt
Sujet de thèse proposé par l'équipe Ordonnancement et Conduite (ERL CNRS 6305) du Laboratoire d'Informatique (EA 6300) de l'Université de Tours.
Titre : Complexité au pire cas de problèmes d'ordonnancement
Directeur de thèse : Vincent T'kindt - email : tkindt@univ-tours.fr
Mots clés : ordonnancement, complexité au pire cas, méthodes exactes.
1. Contexte de la thèse
Traditionnellement, les comparaisons des méthodes de résolutions d'un problème NP-difficile s'effectuent sur leur comportement en moyenne, face à des instances standards ou générées aléatoirement. Dans l'approche envisagée dans ce sujet de thèse, la comparaison s'effectue sur un plan théorique, en utilisant la notation asymptotique O*(.), et elle s'effectue dans le pire des cas. Il faut pour cela répondre à la question :
Étant donné une méthode, destinée à résoudre un problème d'ordonnancement NP-difficile, quelle est la complexité dans le pire des cas de cette méthode, en fonction de la taille de l'instance ?
Répondre à cette question n'est pas chose aisée. Il n'est, par exemple, pas forcément simple de calculer la complexité dans le pire des cas d'une procédure par séparation et évaluation. Les bornes inférieures et les conditions de dominance ne s'appliquent pas systématiquement, et il est très difficile de prédire leur action sur la PSE sans faire d'hypothèses sur l'instance. On est donc amené à imaginer d'autres méthodes de résolutions, peut-être moins efficaces en moyenne, mais dont la complexité dans le pire des cas s'étudie plus simplement. Une question émerge ensuite naturellement :
Étant donné un problème P, NP-difficile, quelle est la méthode résolvant P ayant la plus petite complexité dans le pire des cas ?
La complexité de cette méthode sera alors appelée la complexité dans le pire des cas du problème P.
Mais répondre à cette question reviendrait à répondre à la question « P = NP? » : on essaiera plutôt de trouver une majoration de cette complexité dans le pire des cas. Les méthodes étudiées sont, a priori, exponentielles et c'est la base de l'exponentielle qui déterminera leur rapidité sur de grandes instances.
Ce type d'étude n'est pas nouveau, il a été effectué dès les années 60 sur le problème CNF-SAT [Davis and Putnam, 1960]), sur le problème du voyageur de commerce ([Held and Karp, 1962]) ainsi que sur de nombreux problèmes issus de la théorie des graphes ([Tarjan and Trojanowski, 1977], [Fomin et al., 2006], [Bourgeois et al., 2010]).
Très peu d'études, par contre, ont été menées sur les problèmes d'ordonnancement. En dehors des travaux récents menés au sein des laboratoires des universités de Tours et Orléans, seuls existent quelques résultats sur des problèmes à une machine ([Woeginger, 2003], [Fomin and Kratsch, 2010] et [Cygan et al., 2011]). Ce qui ouvre la voie à de nombreuses directions de recherche.
2. Objectif de la Thèse
L'objectif de la thèse est d'améliorer ou de calculer des complexités au pire cas pour des problèmes d'ordonnancement classiques et de mettre en œuvre les méthodes afin de juger de leur applicabilité pratique, en particulier dans le cas de méthodes de programmation dynamique. Un objectif secondaire sera de caractériser des instances difficiles.
3. Candidat recherché
Le candidat devra avoir un niveau Master avec des bases en Recherche Opérationnelle et être autonome. Le candidat devra avoir en outre de bonnes connaissances en algorithmique, analyse d'algorithmes, calcul de complexité et programmation dynamique. Enfin, des compétences de programmation en C/C++ sont souhaitables.
Références bibliographiques
[Bourgeois et al., 2010] Bourgeois, N., Escoffier, B., Paschos, V., and van Rooij, J. (2010). A bottom-up method and fast algorithms for max independent set. In proceedings of 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Lecture Notes in Comput. Sci., volume 6139, pages 62–73.
[Cygan et al., 2011] Cygan, M., Pilipczuk, M. P. M., and J.O. Wojtaszczyk, J. (2011). In Demetrescu, C. and Halldórsson, M., editors, Algorithms - ESA 2011, volume 6942 of Lecture Notes in Computer Science, pages 299–310. Springer Berlin / Heidelberg.
[Davis and Putnam, 1960] Davis, M. and Putnam, H. (1960). A computing procedure for quantification theory. Journal of the ACM, 7 :201–215.
[Fomin and Kratsch, 2010] Fomin, F. and Kratsch, D. (2010). Exact Exponential Algorithms. Springer.
[Fomin et al., 2006] Fomin, F., Grandoni, F., and D.Kratsch (2006). Measure & conquer : a simple 0(20.288n) independent set algorithm. In proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pages 18–25.
[Held and Karp, 1962] Held, M. and Karp, R. (1962). A dynamic programming approach to sequencing problems. Journal of SIAM, 10 :196–210.
[Tarjan and Trojanowski, 1977] Tarjan, R. and Trojanowski, A. (1977). Finding a maximum independent set. SIAM Journal on Computing, 6 :537–546.
[Woeginger, 2003] Woeginger, G. (2003). Exact algorithms for NP-hard problems : A survey. Pages 185–207.
Titre : Complexité au pire cas de problèmes d'ordonnancement
Directeur de thèse : Vincent T'kindt - email : tkindt@univ-tours.fr
Mots clés : ordonnancement, complexité au pire cas, méthodes exactes.
1. Contexte de la thèse
Traditionnellement, les comparaisons des méthodes de résolutions d'un problème NP-difficile s'effectuent sur leur comportement en moyenne, face à des instances standards ou générées aléatoirement. Dans l'approche envisagée dans ce sujet de thèse, la comparaison s'effectue sur un plan théorique, en utilisant la notation asymptotique O*(.), et elle s'effectue dans le pire des cas. Il faut pour cela répondre à la question :
Étant donné une méthode, destinée à résoudre un problème d'ordonnancement NP-difficile, quelle est la complexité dans le pire des cas de cette méthode, en fonction de la taille de l'instance ?
Répondre à cette question n'est pas chose aisée. Il n'est, par exemple, pas forcément simple de calculer la complexité dans le pire des cas d'une procédure par séparation et évaluation. Les bornes inférieures et les conditions de dominance ne s'appliquent pas systématiquement, et il est très difficile de prédire leur action sur la PSE sans faire d'hypothèses sur l'instance. On est donc amené à imaginer d'autres méthodes de résolutions, peut-être moins efficaces en moyenne, mais dont la complexité dans le pire des cas s'étudie plus simplement. Une question émerge ensuite naturellement :
Étant donné un problème P, NP-difficile, quelle est la méthode résolvant P ayant la plus petite complexité dans le pire des cas ?
La complexité de cette méthode sera alors appelée la complexité dans le pire des cas du problème P.
Mais répondre à cette question reviendrait à répondre à la question « P = NP? » : on essaiera plutôt de trouver une majoration de cette complexité dans le pire des cas. Les méthodes étudiées sont, a priori, exponentielles et c'est la base de l'exponentielle qui déterminera leur rapidité sur de grandes instances.
Ce type d'étude n'est pas nouveau, il a été effectué dès les années 60 sur le problème CNF-SAT [Davis and Putnam, 1960]), sur le problème du voyageur de commerce ([Held and Karp, 1962]) ainsi que sur de nombreux problèmes issus de la théorie des graphes ([Tarjan and Trojanowski, 1977], [Fomin et al., 2006], [Bourgeois et al., 2010]).
Très peu d'études, par contre, ont été menées sur les problèmes d'ordonnancement. En dehors des travaux récents menés au sein des laboratoires des universités de Tours et Orléans, seuls existent quelques résultats sur des problèmes à une machine ([Woeginger, 2003], [Fomin and Kratsch, 2010] et [Cygan et al., 2011]). Ce qui ouvre la voie à de nombreuses directions de recherche.
2. Objectif de la Thèse
L'objectif de la thèse est d'améliorer ou de calculer des complexités au pire cas pour des problèmes d'ordonnancement classiques et de mettre en œuvre les méthodes afin de juger de leur applicabilité pratique, en particulier dans le cas de méthodes de programmation dynamique. Un objectif secondaire sera de caractériser des instances difficiles.
3. Candidat recherché
Le candidat devra avoir un niveau Master avec des bases en Recherche Opérationnelle et être autonome. Le candidat devra avoir en outre de bonnes connaissances en algorithmique, analyse d'algorithmes, calcul de complexité et programmation dynamique. Enfin, des compétences de programmation en C/C++ sont souhaitables.
Références bibliographiques
[Bourgeois et al., 2010] Bourgeois, N., Escoffier, B., Paschos, V., and van Rooij, J. (2010). A bottom-up method and fast algorithms for max independent set. In proceedings of 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Lecture Notes in Comput. Sci., volume 6139, pages 62–73.
[Cygan et al., 2011] Cygan, M., Pilipczuk, M. P. M., and J.O. Wojtaszczyk, J. (2011). In Demetrescu, C. and Halldórsson, M., editors, Algorithms - ESA 2011, volume 6942 of Lecture Notes in Computer Science, pages 299–310. Springer Berlin / Heidelberg.
[Davis and Putnam, 1960] Davis, M. and Putnam, H. (1960). A computing procedure for quantification theory. Journal of the ACM, 7 :201–215.
[Fomin and Kratsch, 2010] Fomin, F. and Kratsch, D. (2010). Exact Exponential Algorithms. Springer.
[Fomin et al., 2006] Fomin, F., Grandoni, F., and D.Kratsch (2006). Measure & conquer : a simple 0(20.288n) independent set algorithm. In proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pages 18–25.
[Held and Karp, 1962] Held, M. and Karp, R. (1962). A dynamic programming approach to sequencing problems. Journal of SIAM, 10 :196–210.
[Tarjan and Trojanowski, 1977] Tarjan, R. and Trojanowski, A. (1977). Finding a maximum independent set. SIAM Journal on Computing, 6 :537–546.
[Woeginger, 2003] Woeginger, G. (2003). Exact algorithms for NP-hard problems : A survey. Pages 185–207.