DÜRR Christoph

Director of research
Team : RO

Sorbonne Université - LIP6

Tel: +33 1 44 27 87 39, Christoph.Durr (at) nulllip6.fr
https://webia.lip6.fr/~durrc/

Three past PhD students (2014 - 2022) at Sorbonne University

Two past Postdoc (2014 - 2022) at Sorbonne University

2005-2024 Publications

2024
- S. Angelopoulos, Ch. Dürr, A. Elenter, G. Melidi : “Scenario-Based Robust Optimization of Tree Structures”, (2024)
- S. Angelopoulos, M. Bienkowski, Ch. Dürr, B. Simon : “Contract Scheduling with Distributional and Multiple Advice”, Proceedings of the 33^rd International Joint Conference in Artificial Intelligence (IJCAI-24), Jeju Island, Korea, Republic of (2024)
- S. Angelopoulos, Ch. Dürr, A. Elenter, Y. Lefki : “Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms”, Proceedings of The Thirty-Eighth Annual Conference on Neural Information Processing Systems (NeurIPS 2024), Vancouver, BC, Canada (2024)
- S. Angelopoulos, Ch. Dürr, Sh. Jin, Sh. Kamali, M. Renault : “Online Computation with Untrusted Advice”, Journal of Computer and System Sciences, (Elsevier) (2024)
2023
- S. Angelopoulos, Ch. Dürr, Sh. Jin : “Best-of-both-Worlds Analysis of Online Search”, Algorithmica, (Springer Verlag) (2023)
- Ch. Dürr, M. Mari, U. Schmidt‑Kraepelin : “On price-induced minmax matchings”, (2023)
2022
- F. Dufossé, Ch. Dürr, N. Nadal, D. Trystram, Ó. Vásquez : “Scheduling with a processing time oracle”, Applied Mathematical Modelling, vol. 104, pp. 701-720, (Elsevier) (2022)
2021
- E. Bampis, Ch. Dürr, Th. Erlebach, M. Santos De Lima, N. Megow, J. Schlöter : “Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty”, 29^th Annual European Symposium on Algorithms (ESA 2021), vol. 204, Leibniz International Proceedings in Informatics (LIPIcs), Lisboa, Portugal, pp. 10:1-10:18, (Schloss Dagstuhl -- Leibniz-Zentrum für Informatik) (2021)
- M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, Ch. Dürr, L. Folwarczný, Ł. Jeż, J. Sgall, N. Thang, P. Veselý : “New results on multi-level aggregation”, Theoretical Computer Science, vol. 861, pp. 133-143, (Elsevier) (2021)
- Ch. Dürr, Sh. Kamali : “Randomized Two-Valued Bounded Delay Online Buffer Management”, Operations Research Letters, vol. 49 (2), pp. 246-249, (Elsevier) (2021)
- Ch. Dürr, J.‑J. Vie : “Competitive Programming in Python,128 Algorithms to Develop your Coding Skills”, (2021)
- Ch. Dürr, K. Nguyen, A. Srivastav, L. Tible : “Non-monotone DR-submodular Maximization over General Convex Sets”, Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}, Yokohama, Japan, pp. 2148-2154, (International Joint Conferences on Artificial Intelligence Organization) (2021)
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)
- Ch. Dürr, Th. Erlebach, N. Megow, J. Meissner : “An Adversarial Model for Scheduling with Testing”, Algorithmica, (Springer Verlag) (2020)
- M. Chrobak, Ch. Dürr, A. Fabijan, B. Nilsson : “Online Clique Clustering”, Algorithmica, vol. 82 (4), pp. 938-965, (Springer Verlag) (2020)
- M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, Ch. Dürr, L. Folwarczný, T. Jez, J. Sgall, K. Nguyen, P. Veselý : “Online algorithms for multilevel aggregation”, Operations Research, vol. 68 (1), pp. 214-232, (INFORMS) (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
- Ch. Dürr, J.‑J. Vie : “書名：培養與鍛鍊程式設計的邏輯腦：程式設計大賽的128個進階技巧(使用Python)”, (ISBN: 978-986-434-383-6) (2019)
- S. Angelopoulos, Ch. Dürr, Th. Lidbetter : “The expanding search ratio of a graph”, Discrete Applied Mathematics, vol. 260, pp. 51-65, (Elsevier) (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. Kamali, M. Renault, A. Rosén : “Online Bin Packing with Advice of Small Size”, Theory of Computing Systems, vol. 62 (8), pp. 2006-2034, (Springer Verlag) (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)
- Ch. Dürr, J.‑J. Vie : “高效算法”, (ISBN: 9787115480859) (2018)
- Ch. Dürr, Th. Erlebach, N. Megow, J. Meissner : “Scheduling with Explorable Uncertainty”, 9^th Innovations in Theoretical Computer Science Conference (ITCS 2018), vol. 94, Leibniz International Proceedings in Informatics (LIPIcs), Cambridge, United States, pp. 30:1-30:14, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2018)
2017
- Ch. Dürr, Ł. Jeż, Ó. Vásquez : “Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling”, Theoretical Computer Science, vol. 695, pp. 28-41, (Elsevier) (2017)
- N. Bansal, Ch. Dürr, N. Thang, O. Vasquez Perez : “The local–global conjecture for scheduling with non-linear cost”, Journal of Scheduling, vol. 20 (3), pp. 239-254, (Springer Verlag) (2017)
- Ch. Dürr, Th. Erlebach, N. Megow, M. Julie : “An Adversarial Model for Scheduling with Testing”, Proceedings of the 13^th Workshop on Models and Algorithms for Planning and Scheduling Problems, Seeon, Germany, pp. 68-70 (2017)
- Ch. Dürr, Z. Hanzalek, Ch. Konrad, Y. Seddik, R. Sitters, O. Vasquez Perez, Gerhard J. Woeginger : “The triangle scheduling problem”, Journal of Scheduling, (Springer Verlag) (2017)
- S. Angelopoulos, D. Arsenio, Ch. Dürr : “Infinite linear programming and online searching with turn cost”, Theoretical Computer Science, (Elsevier) (2017)
2016
- Ch. Dürr, Ch. Konrad, M. Renault : “On the Power of Advice and Randomization for Online Bipartite Matching”, Proc. of the 24^th European Symposium on Algorithms (ESA), Aarhus, Denmark (2016)
- M. Bienkowski, M. Böhm, J. Byrka, M. Chrobak, Ch. Dürr, L. Folwarczný, Ł. Jeż, J. Sgall, K. Nguyen, P. Veselý : “Online Algorithms for Multi-Level Aggregation”, Proc. of the 24^th European Symposium on Algorithms (ESA), Aarhus, Denmark (2016)
- Ch. Dürr, J.‑J. Vie : “Programmation efficace: 128 algorithmes qu’il faut avoir compris et codes en Python au cours de sa vie”, (ellipses), (ISBN: 9782340-010055) (2016)
- S. Angelopoulos, Ch. Dürr, Th. Lidbetter : “The expanding search ratio of a graph”, Proc. of the 33^rd Symposium on Theoretical Aspects of Computer Science (STACS), vol. 47, Leibniz International Proceedings in Informatics (LIPIcs), Orléans, France, pp. 4:1-9:14, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2016)
- S. Angelopoulos, D. Arsenio, Ch. Dürr, A. López‑Ortiz : “Multi-processor Search and Scheduling Problems with Setup Cost”, Theory of Computing Systems, (Springer Verlag) (2016)
2015
- Ch. Dürr, Ł. Jeż, O. Vasquez Perez : “Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption”, Discrete Applied Mathematics, vol. 196, pp. 20-27, (Elsevier) (2015)
- S. Angelopoulos, Ch. Dürr, Sh. Kamali, M. Renault, A. Rosén : “Online Bin Packing with Advice of Small Size”, Algorithms and Data Structures, vol. 9214, Lecture Notes in Computer Science, Victoria, Canada, pp. 40-53, (Springer) (2015)
- M. Chrobak, Ch. Dürr, B. Nilsson : “Competitive Strategies for Online Clique Clustering”, The 9^th International Conference on Algorithms and Complexity (CIAC), Paris, France, pp. 101-113 (2015)
- O. Bellenguez‑Morineau, M. Chrobak, Ch. Dürr, D. Prot : “A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines”, Journal of Scheduling, vol. 18 (3), pp. 299-304, (Springer Verlag) (2015)
2014
- Ch. Dürr, W. Thomas : “STACS 2012 Special Issue”, Symposium on Theoretical Aspects of Computer Science (STACS), vol. 55 (4), Theory of Computing Systems, Paris, France, (Springer) (2014)
- Ch. Dürr : “Tutoriel : Gestion de tampon en ligne”, ROADEF - 15^e congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Bordeaux, France (2014)
- Ch. Dürr, O. Vasquez Perez : “Order constraints for single machine scheduling with non-linear cost”, 16^th Workshop on Algorithm Engineering and Experiments (ALENEX 2014), Portland, United States, pp. 98-111, (SIAM) (2014)
2013
- Ch. Dürr, Ł. Jeż, O. Vasquez Perez : “Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling”, WINE 2013: The 9^th Conference on Web and Internet Economics, vol. 8289, Lecture Notes in Computer Science, Cambridge, MA, United States, pp. 134-145, (Springer) (2013)
- Ch. Dürr, F. Guíñez : “The Wide Partition Conjecture and the Atom Problem in Discrete Tomography”, The VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), vol. 44, Electronic Notes in Discrete Mathematics, Playa del Carmen, Mexico, pp. 351-356 (2013)
- Ch. Dürr, Th. Schwentick : “Special Issue on Theoretical Aspects of Computer Science”, Symposium on Theoretical Aspects of Computer Science (STACS), vol. 53 (2), Theory of Computing Systems, Dortmund, Germany, (Springer) (2013)
- M. Bienkowski, M. Chrobak, Ch. Dürr, M. Hurand, A. Jeż, Ł. Jeż, G. Stachowiak : “A $\Phi$-Competitive Algorithm for Collecting Items with Increasing Weights from a Dynamic Queue”, Theoretical Computer Science, vol. 475, pp. 92-102, (Elsevier) (2013)
- M. Bienkowski, M. Chrobak, Ch. Dürr, M. Hurand, A. Jeż, Ł. Jeż, G. Stachowiak : “Collecting Weighted Items from a Dynamic Queue”, Algorithmica, vol. 65 (1), pp. 60-94, (Springer Verlag) (2013)
2012
- E. Bampis, Ch. Dürr, F. Kacem, Ioannis Z. Milis : “Speed scaling with power down scheduling for agreeable deadlines”, Sustainable Computing : Informatics and Systems, vol. 2 (4), pp. 184-189, (Elsevier) (2012)
- Ch. Dürr, Ł. Jeż, N. Thang : “Online Scheduling of Bounded Length Jobs to Maximize Throughput”, Journal of Scheduling, vol. 15 (5), pp. 653-664, (Springer Verlag) (2012)
- M. Chrobak, Ch. Dürr, F. Guíñez, A. Lozano, N. Thang : “Tile Packing Tomography is {NP}-hard”, Algorithmica, vol. 64 (2), pp. 267-278, (Springer Verlag) (2012)
- Ph. Baptiste, M. Chrobak, Ch. Dürr : “Polynomial Time Algorithms for Minimum Energy Scheduling”, ACM Transactions on Algorithms, vol. 8 (3), pp. 26, (Association for Computing Machinery) (2012)
- Ch. Dürr, M. Queyranne, Frits C. R. Spieksma, F. Nobibon, Gerhard J. Woeginger : “The interval ordering problem”, Discrete Applied Mathematics, vol. 160 (7-8), pp. 1094-1103, (Elsevier) (2012)
- J. Cohen, Ch. Dürr, K. Nguyen : “Smooth inequalities and equilibrium inefficiency in scheduling games”, 8^th International Workshop on Internet and Network Economics (WINE 2012), vol. 7695, Lecture Notes in Computer Science, Liverpool, United Kingdom, pp. 350-363 (2012)
- Ch. Dürr, I. Milis, J. Robert, G. Zois : “Approximating the Throughput by Coolest First Scheduling”, Approximation and Online Algorithms, Ljubljana, Slovenia, pp. 187-200, (Springer) (2012)
- Ch. Dürr, Th. Wilke : “Proceedings of the 29^th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)”, Leibniz International Proceedings in Informatics (LIPIcs) (2012)
- Ch. Dürr, F. Guíñez, M. Matamala : “Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography”, SIAM Journal on Discrete Mathematics, vol. 26 (1), pp. 330-352, (Society for Industrial and Applied Mathematics) (2012)
2011
- M. Chrobak, Ch. Dürr, M. Hurand, J. Robert : “Algorithms for temperature-aware task scheduling in microprocessor systems”, Sustainable Computing : Informatics and Systems, vol. 1 (3), pp. 241-247, (Elsevier) (2011)
- J. Cohen, Ch. Dürr, N. Thang : “Non-clairvoyant Scheduling Games”, Theory of Computing Systems, vol. 49 (1), pp. 3-23, (Springer Verlag) (2011)
- Ch. Dürr, Th. Schwentick : “Proceedings of the 28^th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)”, Symposium on Theoretical Aspects of Computer Science (STACS), vol. 9, Leibniz International Proceedings in Informatics (LIPIcs), Dortmund, Germany, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik), (ISBN: 978-3-939897-25-5) (2011)
- Ch. Dürr, M. Hurand : “Finding total unimodularity in optimization problems solved by linear programs”, Algorithmica, vol. 59 (2), pp. 256-268, (Springer Verlag) (2011)
- E. Bampis, Ch. Dürr, F. Kacem, I. Milis : “Speed scaling with power down scheduling for agreeable deadlines”, (2011)
2007
- Ph. Baptiste, P. Brucker, M. Chrobak, Ch. Dürr, S. Kravchenko, F. Sourd : “The Complexity of Mean Flow Time Scheduling Problems with Release Times”, Journal of Scheduling, vol. 10 (2), pp. 139-146, (Springer Verlag) (2007)
2005
- Ph. Baptiste, M. Chrobak, Ch. Dürr, F. Sourd : “Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow-Time”, MAPSP 2005 - 7^th workshop on Models and Algorithms for Planning and Scheduling Problems, Siena, Italy, pp. 36-38 (2005)