JIN Shendan

doctorant à Sorbonne Université
Équipe : RO
https://perso.lip6.fr/Shendan.Jin

Direction de recherche : Christoph DÜRR

Algorithmes en ligne avec re-optimisation

Le but de la thèse est de développer des algorithmes en ligne dans le modèle où l'algorithme peut revenir sur ses décisions moyennant un coût (re-optimisation, ou en anglais recourse actions). En particulier nous souhaitons travailler sur le problème d'acceptation de demandes de connections dans un réseau à capacité limité (en anglais online routing ou admission control), ainsi que des variantes du problème de Steiner. L'algorithmique en ligne dispose d'un outil puissant, l'approche primale-duale, qui permet d'analyser et de concevoir de manière systématique des algorithmes en ligne. La thèse s'efforcera d'étendre cette technique à des modèles avec re-optimisation.

Soutenance : 18/05/2020

Membres du jury :

M. Spyros Angelopoulos, Chargé de recherche, LIP6, Sorbonne Université
M. Evripidis Bampis, Professeur, LIP6, Sorbonne Université
Mme. Cristina Bazgan, Professeur, LAMSADE, Université Paris-Dauphine
M. Christoph Dürr, Directeur de recherche, LIP6, Sorbonne Université
Mme. Claire Mathieu, Directrice de recherche, IRIF, CNRS
M. Christophe Picouleau, Professeur, CNAM-CEDRIC

Date de départ : 31/01/2020

Publications 2018-2024

  • 2024
  • 2023
  • 2020
    • Sh. Jin : “Algorithmes en ligne avec re-optimisation”, soutenance de thèse, soutenance 18/05/2020, direction de recherche Dürr, Christoph (2020)
    • S. Angelopoulos, Ch. Dürr, Sh. Jin : “Online maximum matching with recourse”, Journal of Combinatorial Optimization, vol. 40 (4), pp. 974-1007, (Springer Verlag) (2020)
    • S. Angelopoulos, Ch. Dürr, Sh. Kamali, Sh. Jin, M. Renault : “Online Computation with Untrusted Advice”, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), vol. 151, Leibniz International Proceedings in Informatics (LIPIcs), Seattle, United States, pp. 52:1-52:15, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2020)
  • 2019
    • S. Angelopoulos, Sh. Jin : “Earliest-Completion Scheduling of Contract Algorithms with End Guarantees”, Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}, Macao, Macao, pp. 5493-5499, (International Joint Conferences on Artificial Intelligence Organization) (2019)
    • S. Angelopoulos, Ch. Dürr, Sh. Jin : “Best-Of-Two-Worlds Analysis of Online Search”, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), vol. 126, Leibniz International Proceedings in Informatics (LIPIcs), Berlin, Germany, pp. 7:1-7:17, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2019)
  • 2018
    • S. Angelopoulos, Ch. Dürr, Sh. Jin : “Online Maximum Matching with Recourse”, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), vol. 117, Leibniz International Proceedings in Informatics (LIPIcs), Liverpool, United Kingdom, pp. 8:1-8:15 (2018)