Workshop — New Techniques in Online Algorithms


Thursday, Nov 12

morning session
9:00-9:15 reception and coffee
9:15-10:00 Claire Mathieu (CNRS and ENS): The carpool problem
10:05-10:25 Guy Even (Tel-Aviv University): Better deterministic online packet routing on grids 
10:25-10:45 coffee break
10:45-11:05 Vincent Cohen-Addad (ENS): The k-center problem in the sliding window model
11:10-11:30  Marc Renault (UPMC Paris 6): Online Bin Packing with Small Advice
11:35-11:55 Jérémie Leguay (Huawei): Admission Control with Online Algorithms in SDN
afternoon session
14:00-14:45 Joan Boyar (IMADA Denmark): Advice complexity for a class of online problems
14:50-15:10 Dennis Komm (ETH Zürich): k-Server, advice, and its implications
15:10-15:30 coffee break
15:30-15:50 Nguyen Kim Thang (Evry): Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
15:55-16:15  Christian Kudahl (IMADA Denmark): On The Advice Complexity of Hereditary Graph Problems
16:20-16:40 Jesper With Mikkelsen (IMADA Denmark): Randomization versus advice
16:40-          open problems session
20:00 restaurant chez Papa 12, 40 boulevard de la Bastille, métro Bastille, easy walk from Jussieu.

Friday, Nov 13

morning session
9:00-9:15 coffee
9:15-9:35 Rob van Stee (University of Leicester): The latest news in online bin packing
9:40-10:20 Dimitris Fotakis (National Technical University of Athens): Online Sum-Radii Clustering
10:20-11:00 coffee break
11:00-11:20 Spyros Angelopoulos (CNRS and UPMC): The expanding search ratio of a graph
11:25-11:45 Shahin Kamali (MIT): Practical applications of online bin packing
afternoon session
14:00-14:20 Hans-Joachim Böckenhauer (ETH Zürich): Advice complexity of the knapsack problem
14:25-14:45 Jiří Sgall (Charles University, Prague): Online Algorithms for Multi-Level Aggregation
14:50-15:10 Christoph Dürr (CNRS and UPMC): Competitive Strategies for Online Clique Clustering


University Pierre et Marie Curie, Paris 06.
Tower 26,
Room 25-26/105

how to get there (tower 26 is on the left as you enter the campus)


Register here by November 7, 2015.  Registration is mandatory, but there are no registration fees. 
There is no need to register if you appear on the following list.

List of participants

  • Adi Rosén (LIAFA Paris 7)
  • Christian Konrad (Reykjavik University)
  • Christian Kudahl (IMADA Denmark)
  • Christoph Dürr (CNRS and UPMC)
  • Claire Mathieu (CNRS and ENS)
  • Dennis Komm (ETH Zürich)
  • Dimitris Fotakis (National Technical University of Athens)
  • Evripidis Bampis (UPMC Paris 6)
  • Frederik Mallmann (ENS)
  • Giorgio Lucarelli (University of Grenoble-Alpes)
  • Guy Even (Tel-Aviv University)
  • Hans-Joachim Böckenhauer (ETH Zürich)
  • Ioannis Millis (Athens University of Economics and Business)
  • Jérémie Leguay (Huawei)
  • Jesper With Mikkelsen (IMADA Denmark)
  • Jiří Sgall (Charles University, Prague)
  • Joan Boyar (IMADA Denmark)
  • Kim S. Larsen (IMADA Denmark)
  • Lene Monrad Favrholdt (IMADA Denmark)
  • Marc Renault (LIAFA Paris 7)
  • Martin Derka (University of Waterloo)
  • Michael Lampis (LAMSADE Paris Dauphine)
  • Michal Kotrbcik (Masaryk University, Brno)
  • Moez Draief (Huawei)
  • Nguyen Kim Thang (IBISC, Université d'Evry)
  • Pavel Veselý (Charles University, Prague)
  • Rob van Stee (University of Leicester)
  • Sandy Heydrich (Max Planck Institute for Informatics)
  • Shahin Kamali (MIT)
  • Shikha Singh (Stony Brook University and IBISC, Université d'Evry)
  • Spyros Angelopoulos (CNRS and UPMC)
  • Sushmita Gupta (University of Bergen)
  • Vincent Cohen-Addad (ENS)

    Some hotels

    For your information, the November 11 is a national holiday in France. Here is a list of hotels with which we have some experience and that we recommend. The prices are probably a bit outdated.

    High standard


    Lower range


    you can upload your slides below.
    Christoph Dürr,
    Nov 13, 2015, 3:06 AM
    Christoph Dürr,
    Nov 13, 2015, 7:14 AM
    Christoph Dürr,
    Nov 13, 2015, 3:05 AM
    Spyros Angelopoulos,
    Nov 16, 2015, 9:24 AM
    Christoph Dürr,
    Nov 13, 2015, 3:04 AM
    Christoph Dürr,
    Nov 12, 2015, 3:07 AM
    Christoph Dürr,
    Nov 13, 2015, 1:05 PM
    Spyros Angelopoulos,
    Dec 1, 2015, 5:11 AM
    Christoph Dürr,
    Nov 13, 2015, 7:14 AM