1 PhD student (Supervision / Co-supervision)

• TYDRICHOVA Magdaléna : Algorithmique des préférences structurées en décision collective : reconnaissance et optimisation

1 PhD graduated 2020

2004-2020 Publications

• 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)
  • T. Allouche, B. Escoffier, S. Moretti, M. Öztürk : “Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions”, Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International 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)