JIN Shendan

PhD graduated
Team : RO
Departure date : 01/31/2020
https://lip6.fr/Shendan.Jin

Supervision : 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.

Defence : 05/18/2020 - 14

Jury members :

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

2018-2020 Publications

  • 2020
    • Sh. Jin : “Algorithmes en ligne avec re-optimisation”, thesis, defence 05/18/2020, supervision 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)