ESCOFFIER Bruno

Full Professor
Team : RO

Sorbonne Université - LIP6

Tel: +33 1 44 27 72 09, Bruno.Escoffier (at) nulllip6.fr
https://webia.lip6.fr/~escoffier

2 PhD students (Supervision / Co-supervision)

BRUNOD INDRIGO Luca : Aspects algorithmiques pour l’ancrage de décisions en optimisation sous incertitude
XEFTERIS Michail : Multistage optimization and prediction

2 PhD graduated 2020 - 2023

2004-2023 Publications

2023
- B. Escoffier, O. Spanjaard, M. Tydrichová : “Algorithmic Recognition of 2-Euclidean Preferences”, Proceedings of ECAI 2023, vol. 372, Frontiers in Artificial Intelligence and Applications, Krakow (Cracovie), Poland, pp. 637-644, (IOS Press), (ISBN: 978-1-64368-437-6) (2023)
- E. Bampis, B. Escoffier, N. Hahn, M. Xefteris : “Online TSP with Known Locations”, Algorithms and Data Structures Symposium (WADS), vol. 14079, Lecture Notes in Computer Science, Montreal, Canada, pp. 65-78, (Springer Nature Switzerland) (2023)
- P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, B. Escoffier : “Algorithms and complexity results for resource leveling problems”, ROADEF, Rennes, France (2023)
- E. Bampis, C.‑E. Cella, B. Escoffier, M. Rocco, A. Teiller : “Target-based computer-assisted orchestration: Complexity and approximation algorithms”, European Journal of Operational Research, vol. 304 (3), pp. 926-938, (Elsevier) (2023)
- E. Bampis, B. Escoffier, Th. Gouleakis, N. Hahn, K. Lakis, G. Shahkarami, M. Xefteris : “Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else”, 31^st Annual European Symposium on Algorithms (ESA 2023), vol. 274, Leibniz International Proceedings in Informatics (LIPIcs), Amsterdam, Netherlands, pp. 12:1-12:17, (Schloss Dagstuhl - Leibniz-Zentrum für Informatik) (2023)
2022
- Th. Ehrhard, S. Attias, E. Bampis, V. Cohen‑Addad, B. Escoffier, C. Mathieu, F. Pascual, A. Pass‑Lanneau, D. Saulpic : “Découpage électoral des circonscriptions législatives en France: déséquilibres démographiques et contraintes territoriales”, Revue Française de Science Politique, vol. Vol. 72 (3), pp. 333-364, (Presses de Sciences Po) (2022)
- E. Bampis, B. Escoffier, M. Xefteris : “Canadian Traveller Problem with Predictions”, 20^th International Workshop on Approximation and Online Algorithms, WAOA 2022, vol. 13538, Lecture Notes in Computer Science, Potsdam, Germany, pp. 116-133 (2022)
- E. Bampis, D. Christou, B. Escoffier, K. Nguyen : “Online learning for min-max discrete problems”, Theoretical Computer Science, vol. 930, pp. 209-217, (Elsevier) (2022)
- B. Escoffier, O. Spanjaard, M. Tydrichová : “Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences”, Discrete Applied Mathematics, vol. 318, pp. 6-12, (Elsevier) (2022)
- B. Escoffier, L. Gourvès, V. Paschos : “In memory of Jérôme Monnot”, Theoretical Computer Science, vol. 921, pp. 1-3, (Elsevier) (2022)
- E. Bampis, B. Escoffier, A. Teiller : “Multistage knapsack”, Journal of Computer and System Sciences, vol. 126, pp. 106-118, (Elsevier) (2022)
- E. Bampis, D. Christou, B. Escoffier, A. Kononov, K. Nguyen : “A simple rounding scheme for multistage optimization”, Theoretical Computer Science, vol. 907, pp. 1-10, (Elsevier) (2022)
- P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, B. Escoffier : “Anchor-robust project scheduling with time-dependent job durations”, (2022)
2021
- B. Escoffier, O. Spanjaard, M. Tydrichová : “Measuring Nearly Single-Peakedness of an Electorate: Some New Insights”, Algorithmic Decision Theory 7^th International Conference, ADT 2021, Toulouse, France, November 3–5, 2021, Proceedings, vol. 13023, Lecture Notes in Computer Science, Toulouse, France, pp. 19-34, (Springer) (2021)
- E. Bampis, B. Escoffier, K. Schewior, A. Teiller : “Online Multistage Subset Maximization Problems”, Algorithmica, vol. 83 (8), pp. 2374-2399, (Springer Verlag) (2021)
2020
- B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms”, Proceedings of the 13^th International Symposium on Algorithmic Game Theory, SAGT 2020, vol. 12283, Lecture Notes in Computer Science, Augsburg, Germany, pp. 291-306, (Springer) (2020)
- B. Escoffier, E. Bampis, A. Kononov : “LP-Based Algorithms for Multistage Minimization Problems”, Approximation and Online Algorithms, WAOA 2020, vol. 12806, Lecture Notes in Computer Science, Pisa, Italy, pp. 1-15, (Springer) (2020)
- T. Allouche, B. Escoffier, S. Moretti, M. Öztürk : “Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions”, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence {IJCAI-PRICAI-20}, Yokohama, Japan, pp. 17-23, (International Joint Conferences on Artificial Intelligence Organization) (2020)
- B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “Iterative Delegations in Liquid Democracy with Restricted Preferences”, AAAI Technical Track: Game Theory and Economic Paradigms, vol. 34 (2), New-York, NY, United States, pp. 1926-1933 (2020)
2019
- B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “The Convergence of Iterative Delegations in Liquid Democracy in a Social Network”, Lecture Notes in Computer Science, vol. 11801, Athènes, Greece, pp. 284-297 (2019)
- B. Escoffier : “Saving colors and Max Coloring: some fixed-parameter tractability results”, Theoretical Computer Science, vol. 758, pp. 30-41, (Elsevier) (2019)
- E. Bampis, B. Escoffier, K. Schewior, A. Teiller : “Online Multistage Subset Maximization Problems”, 27^th Annual European Symposium on Algorithms (ESA 2019), vol. 144, Leibniz International Proceedings in Informatics (LIPIcs), Munich, Germany, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2019)
- E. Bampis, B. Escoffier, A. Teiller : “Multistage Knapsack”, 44^th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), vol. 138, Aachen, Germany, pp. 22:1-22:14, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (2019)
2018
- E. Bampis, B. Escoffier, S. Mladenovic : “Fair resource allocation over time”, AAMAS 2018 - 17^th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, pp. 766-773, (International Foundation for Autonomous Agents and Multiagent Systems) (2018)
- E. Bampis, B. Escoffier, M. Lampis, Vangelis Th. Paschos : “Multistage Matchings”, 16^th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), vol. 101, Leibniz International Proceedings in Informatics (LIPIcs), Malmo, Sweden, pp. 7:1-7:13 (2018)
- É. Bonnet, B. Escoffier, Vangelis Th. Paschos, G. Stamoulis : “Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs”, Discrete Optimization, vol. 27, pp. 26-56, (Elsevier) (2018)
- E. Angel, E. Bampis, B. Escoffier, M. Lampis : “Parameterized Power Vertex Cover”, Discrete Mathematics and Theoretical Computer Science, vol. 20 (2), (DMTCS) (2018)
2017
- B. Escoffier, L. Gourvès, J. Monnot : “The Price of Optimum: Complexity and Approximation for a Matching Game”, Algorithmica, vol. 77 (3), pp. 836-866, (Springer Verlag) (2017)
2016
- B. Escoffier : “Saving colors and Max Coloring: some fixed-parameter tractability results”, Proceedings of WG 2016, 42^nd International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Istanbul, Turkey (2016)
- E. Angel, E. Bampis, B. Escoffier, M. Lampis : “Parameterized Power Vertex Cover”, Graph-Theoretic Concepts in Computer Science, vol. 9941, Lecture Notes in Computer Science, Istanbul, Turkey, pp. 97-108, (Springer) (2016)
- É. Bonnet, B. Escoffier, V. Paschos, G. Stamoulis : “A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs”, LATIN 2016: Theoretical Informatics - 12^th Latin American Symposium, vol. 9644, Lecture Notes in Computer Science, Ensenada, Mexico, pp. 235-248, (Springer) (2016)
- B. Escoffier, Vangelis Th. Paschos, E. Tourniaire : “Super-polynomial approximation branching algorithms”, RAIRO - Operations Research, vol. 50 (4-5), pp. 979-994, (EDP Sciences) (2016)
2015
- É. Bonnet, B. Escoffier, V. Paschos, E. Tourniaire : “Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization”, Algorithmica, vol. 71 (3), pp. 566-580, (Springer Verlag) (2015)
- É. Bonnet, B. Escoffier, E. Kim, V. Paschos : “On Subexponential and FPT-Time Inapproximability”, Algorithmica, vol. 71 (3), pp. 541-565, (Springer Verlag) (2015)
- B. Escoffier, J. Monnot, Vangelis Th. Paschos, M. Xiao : “New results on polynomial inapproximability and fixed parameter approximability of edge dominating set”, Theory of Computing Systems, vol. 56 (2), pp. 330-346, (Springer Verlag) (2015)
2014
- B. Escoffier, V. Paschos, E. Tourniaire : “Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms”, Theoretical Computer Science, vol. 560 (2), pp. 147-157, (Elsevier) (2014)
2013
- B. Escoffier, J. Monnot, F. Pascual, O. Spanjaard : “Truthful many-to-many assignment with private weights”, 8^th International Conference on Algorithms and Complexity (CIAC 2013), vol. 7878, Lecture Notes in Computer Science, Barcelona, Spain, pp. 209-220, (Springer) (2013)
- B. Escoffier, J. Monnot, F. Pascual, O. Spanjaard : “Algorithmes à véracité garantie pour des problèmes de b-couplage dans un graphe biparti”, 14^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, ROADEF 2013, Troyes, France (2013)
- N. Bourgeois, F. Della Croce, V. Paschos, B. Escoffier : “Fast algorithms for min independent dominating set”, Discrete Applied Mathematics, vol. 161 (4-5), pp. 558-572, (Elsevier) (2013)
2012
- B. Escoffier, V. Paschos, E. Tourniaire : “Moderate exponential time approximation and branching algorithms”, (2012)
- É. Bonnet, B. Escoffier, V. Paschos, E. Tourniaire : “Using greediness for parameterization: the case of max and min (k, n − k)-cut”, (2012)
- B. Escoffier, E. Kim, V. Paschos : “Subexponential and FPT-time Inapproximability of Independent Set and Related Problems”, (2012)
2011
- B. Escoffier, L. Gourvès, K. Nguyen, F. Pascual, O. Spanjaard : “Strategy-proof Mechanisms for Facility Location Games with Many Facilities”, 2^nd International Conference on Algorithmic Decision Theory (ADT'11), vol. 6992, Lecture Notes in Artificial Intelligence, Piscataway, NJ, United States, pp. 67-81, (Springer) (2011)
- B. Escoffier, L. Gourvès, K. Nguyen, F. Pascual, O. Spanjaard : “Algorithmes à véracité garantie pour le placement d’installations sur une ligne”, 12^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Saint-Etienne, France (2011)
- B. Escoffier, V. Paschos, E. Tourniaire : “Approximating MAX SAT by moderately exponential algorithms”, (2011)
- N. Boria, N. Bourgeois, B. Escoffier, V. Paschos : “Exponential approximation schemata for some network design problems”, (2011)
2010
- B. Escoffier, L. Gourvès, J. Monnot, O. Spanjaard : “Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation”, European Journal of Operational Research, vol. 205 (1), pp. 19-30, (Elsevier) (2010)
- B. Escoffier, O. Spanjaard : “Dynamic Programming”, chapter in Concepts of Combinatorial Optimization, pp. 71-98, (ISTE -- Wiley), (ISBN: 9781848211476) (2010)
2009
- N. Bourgeois, B. Escoffier, V. Paschos, J. M. M. Van Rooij : “Fast algorithms for max independent set”, (2009)
- N. Bourgeois, F. Della Croce, B. Escoffier, V. Paschos : “Exact algorithms for dominating clique problems”, (2009)
2008
- B. Escoffier, J. Monnot, O. Spanjaard : “Some tractable instances of interval data minmax regret problems”, Operations Research Letters, vol. 36 (4), pp. 424-429, (Elsevier) (2008)
- B. Escoffier, J. Monnot, O. Spanjaard : “Some tractable instances of interval data minmax regret problems: bounded distance from triviality (short version)”, 34^th International Conference on Current Trends in Theory and Practice of Computer Science, vol. 4910, Lecture Notes in Computer Science, Nový Smokovec, Slovakia, pp. 280-291, (Springer-Verlag) (2008)
- G. Ausiello, V. Bonifaci, B. Escoffier : “Complexity and Approximation in Reoptimization”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos : “Efficient approximation of MIN COLORING by moderately exponential algorithms”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos : “Efficient approximation of MIN SET COVER by "low-complexity" exponential algorithms”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos, J. M. M. Van Rooij : “Fast algorithms for MAX INDEPENDENT SET in graphs of small average degree”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos, J. M. M. Van Rooij : “Fast algorithms for max independent set in graphs of small average degree”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos : “An improved exact algorithm for maximum independent set in sparse graphs”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos : “Effcient approximation by “low-complexity” exponential algorithms”, (2008)
- N. Bourgeois, B. Escoffier, V. Paschos : “An improved exact algorithm for maximum independent set in sparse graphs”, (2008)
- J. Lang, B. Escoffier, M. Öztürk : “Single-Peaked consistency and its complexity”, 18^th European Conference on Artificial Intelligence(ECAI'08), Greece, pp. 366-370 (2008)
2007
- B. Escoffier, J. Monnot, O. Spanjaard : “Some tractable instances of interval data minmax regret problems: bounded distance from triviality”, (2007)
- N. Bourgeois, B. Escoffier, V. Paschos : “Efficient approximation by "low-complexity" exponential algorithms”, (2007)
- N. Bourgeois, F. Della Croce, B. Escoffier, C. Murat, V. Paschos : “Probabilistic graph-coloring in bipartite and split graphs (Exented version of cahier du LAMSADE 218)”, (2007)
- B. Escoffier, J. Monnot : “Better differential approximation for symetric TSP”, (2007)
- B. Escoffier, L. Gourvès, J. Monnot : “Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs”, (2007)
- B. Escoffier, V. Paschos : “Structures des classes d’approximation : un état de l’art”, (2007)
- B. Escoffier, M. Milanic, V. Paschos : “Simple and fast reoptimizations for the Steiner tree problem”, (2007)
- N. Bourgeois, F. Della Croce, B. Escoffier, C. Murat, V. Paschos : “Probabilistic graph-coloring in bipartite and split graphs”, (2007)
- B. Escoffier, V. Paschos : “A survey on the structure of approximation classes”, (2007)
- B. Escoffier, J. Monnot : “Better differential approximation for symmetric TSP”, (2007)
- B. Escoffier, V. Paschos : “Structures des classes d’approximation : un état de l’art”, (2007)
- B. Escoffier, M. Milanic, V. Paschos : “Simple and fast reoptimizations for the Steiner tree problem”, (2007)
2006
- B. Escoffier, P. Hammer : “Approximation of Quadratic Set Covering Problem”, (2006)
- M. Demange, B. Escoffier, J. Monnot, V. Paschos, D. De Werra : “Weighted coloring on planar, bipartite and split graphs: complexity and approximation”, (2006)
- B. Escoffier, J. Monnot, V. Paschos : “Weighted coloring: further complexity and approximability results”, (2006)
- C. Demestrescu, B. Escoffier, G. Moruz, A. Ribichini : “Parallel Algorithms are Good for Streaming”, (2006)
- G. Ausiello, B. Escoffier, J. Monnot, V. Paschos : “Reoptimization of minimum and maximum traveling salesman’s tours (février 2006)”, (2006)
- C. Demetrescu, B. Escoffier, G. Moruz, A. Ribichini : “Parallel Algorithms are Good for Streaming”, (2006)
- F. Della Croce, B. Escoffier, V. Paschos : “Improved worst-case complexity for the MIN 3-SET COVERING problem (janvier 2006)”, (2006)
- F. Della Croce, B. Escoffier, V. Paschos : “Improved worst-case complexity for the MIN 3-SET COVERING problem”, (2006)
2005
- B. Escoffier, O. Spanjaard : “Programmation dynamique”, chapitre de Optimisation combinatoire (Volume 1: concepts fondamentaux), pp. 95-124, (Hermès), (ISBN: 2-7462-1038-X) (2005)
- B. Escoffier, V. Paschos : “Completeness in approximation classes beyong APX (septembre 2005)”, (2005)
- B. Escoffier, V. Paschos : “Completeness in approximation classes beyond APX”, (2005)
- G. Ausiello, B. Escoffier, J. Monnot, V. Paschos : “Reoptimization of minimum and maximum travelling salesman’s tours”, (2005)
- F. Della Croce, B. Escoffier, C. Murat, V. Paschos : “Probabilistic coloring of bipartite and split graphs”, (2005)
- C. Bazgan, B. Escoffier, V. Paschos : “Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”, (2005)
- B. Escoffier, V. Paschos : “Differential approximation of MIN SAT, MAX SAT and related problems”, (2005)
2004
- B. Escoffier, V. Paschos : “Differential approximation of MIN SAT, MAX SAT and related problems”, (2004)
- D. De Werra, M. Demange, B. Escoffier, J. Monnot, V. Paschos : “Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation”, ISAAC. 04, France, pp. 896-907, (LNCS 3341-springer verlaag) (2004)
- B. Escoffier, V. Paschos : “An Alternative proof of SAT NP-Completeness”, 10 pages (2004)
- B. Escoffier, V. Paschos : “Differential approximation of MIN SAT, MAX SAT and related problems”, 21 pages (2004)
- B. Escoffier, V. Paschos : “On-line models and algorithms for MAX INDEPENDENT SET”, 16 pages (2004)