Publications 2004-2024

• 2024
  • P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, B. Escoffier : “Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems”, Journal of Scheduling, vol. 27 (6), pp. 587-606, (Springer Verlag) (2024)
  • P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, B. Escoffier : “Anchor-robust project scheduling with non-availability periods”, Discrete Optimization, vol. 54, pp. 100864, (Elsevier) (2024)
  • P. Bendotti, L. Brunod‑Indrigo, Ph. Chrétienne, B. Escoffier : “Anchored rescheduling problem with non-availability periods”, Operations Research Letters, vol. 57, pp. 107201, (Elsevier) (2024)
  • Th. Bellitto, J. Cohen, B. Escoffier, N. Khang, M. Rabie : “Canadian Traveller Problems in Temporal Graphs”, (2024)
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing single-peaked preferences on an arbitrary graph: Complexity and algorithms”, Discrete Applied Mathematics, vol. 348, pp. 301-319, (Elsevier) (2024)
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Euclidean preferences in the plane under $\ell_1$, $\ell_2$ and $\ell_\infty$ norms”, Social Choice and Welfare, (Springer Verlag) (2024)
• 2023
  • E. Bampis, B. Escoffier, P. Youssef : “Online 2-stage stable matching”, Discrete Applied Mathematics, vol. 341, pp. 394-405, (Elsevier) (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)
  • Th. Bellitto, C. Conchon‑Kerjan, B. Escoffier : “Restless Exploration of Periodic Temporal Graphs”, 2^nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023), vol. 257, Leibniz International Proceedings in Informatics (LIPIcs), Pise, Italy, pp. 13:1-13:15, (Schloss Dagstuhl – Leibniz-Zentrum für Informatik) (2023)
  • E. Bampis, B. Escoffier, P. Youssef : “Online 2-stage Stable Matching”, AAMAS 2023, 2023 International Conference on Autonomous Agents and Multiagent Systems, Londres, United Kingdom, pp. 2475-2477, (International Foundation for Autonomous Agents and Multiagent Systems) (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. Angel, E. Bampis, B. Escoffier, M. Lampis : “Parameterized Power Vertex Cover”, Discrete Mathematics and Theoretical Computer Science, vol. 20 (2), (DMTCS) (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)
• 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, Türkiye (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, Türkiye, 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)
  • B. Escoffier, D. Ferraioli, L. Gourvès, S. Moretti : “Designing Budget-Balanced Best-Response Mechanisms for Network Coordination Games”, Algorithmic Game Theory, Aachen, Germany, pp. 207-218 (2013)
  • B. Escoffier, E. Kim, V. Paschos, É. Bonnet : “On Subexponential and FPT-time Inapproximability”, Parameterized and Exact Computation8^th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Nice, France, pp. 54-65 (2013)
  • N. Bourgeois, F. Della Croce, B. Escoffier, V. Paschos : “Fast algorithms for min independent dominating set”, Seventh International Conference on Graphs and Optimization 2010, vol. 161 (4-5), Ovronnaz, Switzerland, pp. 558-572 (2013)
  • N. Boria, N. Bourgeois, B. Escoffier, V. Paschos : “Exponential approximation schemata for some network design problems”, Journal of Discrete Algorithms, vol. 22, (Elsevier) (2013)
  • B. Escoffier, L. Gourvès, J. Monnot : “Fair solutions for some multiagent optimization problems”, Autonomous Agents and Multi-Agent Systems, vol. 26 (2) (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)
  • B. Escoffier, L. Gourvès, J. Monnot, S. Moretti : “Cost allocation protocols for network formation on connection situations”, 6^th International Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS 2012 - proceedings, Cargèse, France, pp. 228-234 (2012)
  • B. Escoffier, V. Paschos, E. Tourniaire : “Approximating MAX SAT by moderately exponential algorithms”, Theory and Applications of Models of Computation - 9^th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings, Beijing, China, pp. 622 (2012)
  • N. Bourgeois, F. Della Croce, B. Escoffier, V. Paschos : “Algorithms for dominating clique problems”, Theoretical Computer Science, vol. 459 (9), (Elsevier) (2012)
  • N. Bourgeois, B. Escoffier, V. Paschos, J. Van Rooij : “Fast Algorithms for max independent set”, Algorithmica, vol. 62 (1), pp. 382-415, (Springer Verlag) (2012)
  • B. Escoffier, L. Gourvès, J. Monnot : “Strategic Coloring of a Graph”, Internet Mathematics, vol. 8 (4) (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 : “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)