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.

Phd defence : 05/18/2020

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-2024 Publications

• 2024
  • S. Angelopoulos, Ch. Dürr, Sh. Jin, Sh. Kamali, M. Renault : “Online Computation with Untrusted Advice”, Journal of Computer and System Sciences, vol. 144, pp. 103545, (Elsevier) (2024)
• 2023
  • S. Angelopoulos, Ch. Dürr, Sh. Jin : “Best-of-both-Worlds Analysis of Online Search”, Algorithmica, (Springer Verlag) (2023)
• 2020
  • Sh. Jin : “Algorithmes en ligne avec re-optimisation”, thesis, phd 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”, 11^th 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”, 36^th 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”, 43^rd 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)