Publications (up to 2018)

Books/Book chapters

  1. An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems. N. Bourgeois, B. Escoffier and V. Th. Paschos, Chapter 15 of the book Combinatorial Optimization: Recent Progress, A.R. Mahjoub Editor, Iste - Wiley and Sons, 2011
  2. Moderately Exponential Approximation. N. Bourgeois, B. Escoffier, V. Th. Paschos and E. Tourniaire, Chapter 16 of the book Combinatorial Optimization: Recent Progress, A.R. Mahjoub Editor, Iste - Wiley and Sons, 2011
  3. Complexity and Approximation in Reoptimization. G. Ausiello, V. Bonifaci and B. Escoffier, Chapter 4 of the book Computability in Context: Computation and Logic in the Real World, S.B. Cooper and A. Sorbi Editors, Imperial College Press, pages 101-130, 2011
  4. Worst-case Complexity. F. Della Croce, B. Escoffier, M. Kaminski and V. Th. Paschos, Chapter 8 of the book Combinatorial optimization - Theoretical Computer Science: Interfaces and Perspectives, Iste - Wiley and Sons, pages 203-240, 2008
  5. Min Weighted Node Coloring Problem. M. Demange, B. Escoffier, J. Monnot, V. Th. Paschos and D. de Werra, Chapter 10 of the book Combinatorial optimization - Theoretical Computer Science: Interfaces and Perspectives, Iste - Wiley and Sons, pages 259-290, 2008
  6. Weighted Edge Coloring. M. Demange, B. Escoffier, G. Lucarelli, J. Monnot, V. Th. Paschos and D. de Werra, Chapter 11 of the book Combinatorial optimization - Theoretical Computer Science: Interfaces and Perspectives, Iste - Wiley and Sons, pages 291-318, John Wiley Publisher, 2008
  7. Programmation dynamique, B. Escoffier and O. Spanjaard, chapter 4 of Optimisation Combinatoire: concepts fondamentaux (vol 1), pages 95-124, Editions Hermes science, 2005 (in French)
  8. Objectif prépa, cours et exercices corrigés de mathématiques, Editions Ellipses, 2001 (in French). 2nd edition, 2009.

International journals

  1. Saving colors and max coloring: some fixed-parameter tractability results, B. Escoffier, Theoretical Computer Science, to appear, 2018. Preliminary version.
  2. Parameterized Power Vertex Cover, Eric Angel, Evripidis Bampis, Bruno Escoffier, Michael Lampis: Discrete Mathematics & Theoretical Computer Science 20(2), 2018
  3. Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs, E. Bonnet, B. Escoffier, V. Th. Paschos, G. Stamoulis. Discrete Optimization 27: 26-56, 2018. Preliminary version.
  4. The Price of Optimum: Complexity and Approximation for a Matching Game, B. Escoffier, L. Gourvès, J. Monnot, Algorithmica 77(3): 836-866, 2017. Preliminary version.
  5. Super-polynomial approximation branching algorithms, B. Escoffier, V. Th. Paschos and E. Turniaire, RAIRO - Operations Research 50(4-5): 979-994, 2016. Preliminary version.
  6. New results on polynomial inapproximability and fixed parameter approximability of edge dominating set, B. Escoffier, J. Monnot, V. Th. Paschos and M. Xiao, Theory of Computing Systems 56(2): 330-346, 2015. Preliminary version.
  7. On subexponential and FPT-time inapproximability, E. Bonnet, B. Escoffier, E. Kim and V. Th. Paschos, Algorithmica, 71(3): 541-565, 2015. Preliminary version.
  8. Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization, E. Bonnet, B. Escoffier, V. Th. Paschos and E. Tourniaire, Algorithmica, 71(3): 566-580, 2015. Preliminary version.
  9. Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms, B. Escoffier, V. Th. Paschos and E. Tourniaire, Theoretical Computer Science 560: 147-157, 2014. Preliminary version.
  10. Exponential approximation schemata for some network design problems, N. Boria, N. Bourgeois, B. Escoffier and V. Th. Paschos, Journal of Discrete Algorithms 22:43-52, 2013. Preliminary version.
  11. Fast algorithms for min independent dominating set, N. Bourgeois, F. Della Croce, B. Escoffier and V. Th. Paschos, Discrete Applied Mathematics 161(4-5):558-572, 2013. Preliminary version.
  12. Moderately exponential time and fixed parameter approximation, B. Escoffier, V. Th. Paschos and E. Tourniaire, Optimization 62(8): 1019-1036, 2013.
  13. Fair solutions for some multiagent optimization problems, B. Escoffier, L. Gourvès and J. Monnot, Journal of Autonomous Agents and Multi-Agent Systems 26 (2): 184-201, 2013. Preliminary version.
  14. Algorithms for dominating clique problems, N. Bourgeois, F. Della Croce, B. Escoffier and V. Th. Paschos, Theoretical Computer Science 459: 77-88, 2012. Preliminary version.
  15. Strategic Coloring of a Graph, B. Escoffier, L. Gourvès and J. Monnot, Internet Mathematics 8 (4): 424-455, 2012. Preliminary version.
  16. Fast Algorithms for max independent set, N. Bourgeois, B. Escoffier, V. Th. Paschos and J.M.M Van Rooij, Algorithmica 62 (1-2): 382-415, 2012. Preliminary version.
  17. Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, N. Bourgeois, B. Escoffier and V. Th. Paschos, Discrete Applied Mathematics 159 (17): 1954-1970, 2011. Preliminary version.
  18. Adapting parallel algorithms to the W-Stream model, with applications to graph problems, C. Demetrescu, B. Escoffier, G. Moruz and A. Ribichini, Theoretical Computer Science 411 (44-46): 3994-4004, 2010. Preliminary version.
  19. Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation, B. Escoffier, L. Gourvès, J. Monnot and O. Spanjaard, European Journal of Operations Research 205:19-30, 2010. Preliminary version.
  20. A survey on the structure of approximation classes, B. Escoffier and V. Th. Paschos, Computer Science Review 4(1):19-40, 2010. Preliminary version.
  21. Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, B. Escoffier, L. Gourvès and J. Monnot, Journal of Discrete Algorithms 8(1):36-49, 2010. Preliminary version.
  22. Reoptimization of minimum and maximum traveling salesman’s tours, G. Ausiello, B. Escoffier, J. Monnot and V. Th. Paschos, Journal of Discrete Algorithms 7(4):453-463, 2009. Preliminary version.
  23. Simple and Fast Reoptimizations for the Steiner Tree Problem, B. Escoffier, M. Milanic and V. Th. Paschos, Algorithmic Operations Research 4(2): 86-94, 2009. Preliminary version.
  24. Approximation of Min Coloring by moderately exponential algorithms, N. Bourgeois, B. Escoffier and V. Th. Paschos, Information Processing Letters 109(16): 950-954, 2009. Preliminary version.
  25. Efficient approximation of Min Set Cover by moderately exponential algorithms, N. Bourgeois, B. Escoffier and V. Th. Paschos, Theoretical Computer Science 410(21-23): 2184-2195, 2009. Preliminary version.
  26. Weighted coloring on planar, bipartite and split graphs: complexity and approximation, D. de Werra, M. Demange, B. Escoffier J. Monnot and V. Th. Paschos, Discrete Applied Mathematics 157(4): 819-832, 2009 (preliminary version in Annales du Lamsade n°4-5). Preliminary version.
  27. Probabilistic graph-coloring in bipartite and split graphs, N. Bourgeois, F. Della Croce, B. Escoffier, C. Murat et V. Th. Paschos. Journal of Combinatorial Optimization 17: 274-311, 2009. Preliminary version.
  28. A better differential approximation ratio for symmetric TSP, B. Escoffier and J. Monnot. Theoretical Computer Science 396(1-3): 63-70, 2008. Preliminary version.
  29. Some tractable instances of interval data minmax regret problems: bounded distance from triviality, B. Escoffier, J. Monnot et O. Spanjaard. Operations Research Letters 36: 424–429, 2008. Preliminary version.
  30. Approximation of the Quadratic Set Covering Problem, B. Escoffier et P. Hammer. Discrete Optimization 4(3-4), pages 378-386, 2007. Preliminary version.
  31. Improved worst-case complexity for the MIN 3-SET COVERING problem, B. Escoffier, F. Della Croce and V. Th. Paschos. Operations Research Letters 35(2), pages 205-210, 2007. Preliminary version.
  32. Differential approximation of Max SAT, Min SAT and related problems, B. Escoffier and V. Th. Paschos, European Journal of Operations Research 181(2), pages 620-633, 2007. Preliminary version.
  33. Completeness in approximation classes beyond APX, B. Escoffier and V. Paschos. Theoretical Computer Science 359 (1-3): 369-377 (2006). Preliminary version.
  34. On-line models and algorithms for max independent set, B. Escoffier and V. Th. Paschos, RAIRO Operations Research 40 (2): 129-142 (2006). Preliminary version.
  35. Weighted Coloring: further complexity and approximations results, B. Escoffier, J. Monnot and V. Th. Paschos. Information Processing Letters 97(3): 98-103 (2006). Preliminary version.
  36. Poly-APX- and PTAS-completeness in standard and differential approximation, C. Bazgan, B. Escoffier and V. Th. Paschos, Theoretical Computer Science 339 (2-3): 272-292, 2005. Preliminary version.
  37. Proving completeness by logic, B. Escoffier and V. Th. Paschos, International Journal of Computer Mathematics, 82 (2):151-161, 2005. Preliminary version.

International conferences

  1. Fair resource allocation over time , E. Bampis, B. Escoffier, S. MLadenovic AAMAS 2018. Preliminary version.
  2. Multistage Matchings, E. Bampis, B. Escoffier, M. Lampis, V. Th. Paschos: SWAT 2018: 7:1-7:13.
  3. Parameterized Power Vertex Cover , E. Angel, E. Bampis, B. Escoffier, M. Lampis, WG'16, LNCS 9941, 97-108, 2016.
  4. Saving Colors and Max Coloring: some fixed-parameter tractability results , B. Escoffier, WG'16, LNCS 9941, 50-61, 2016
  5. A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs. E. Bonnet, B. Escoffier, V. Th. Paschos, G. Stamoulis, LATIN'16, LNCS 9644:235-248, 2016
  6. Truthful many-to-many assignment with provate weights, B. Escoffier, J. Monnot, F. Pascual, O. Spanjaard, CIAC'13, LNCS 7878: 209-220, 2013. Preliminary version.
  7. On subexponential and FPT-time inapproximability, E. Bonnet, B. Escoffier, E. Kim, V. Paschos, IPEC'13, LNCS 8246: 54-65, 2013.
  8. Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization, E. Bonnet, B. Escoffier, V. Paschos, E. Tourniaire IPEC'13, LNCS 8246: 66-77, 2013.
  9. Designing budget balanced best-response mechanisms for network coordination games, B. Escoffier, D. Ferraioli, L. Gourvès, S. Moretti SAGT'13, LNCS 8146: 207-218, 2013.
  10. New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, B. Escoffier, J. Monnot, V. Paschos, M. Xiao, IPEC'12, LNCS 7535: 25-36, 2012.
  11. Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms, Bruno Escoffier, Vangelis Th. Paschos and Emeric Tourniaire, TAMC'12, LNCS 7287: 202-213, 2012.
  12. Cost allocation protocols for network formation on connection situations, B. Escoffier, L. Gourvès, J. Monnot, ValueTools'12, IEEE: 228-234, 2012. Preliminary version.
  13. The price of optimum in a matching game, B. Escoffier, L. Gourvès, J. Monnot, SAGT'11, LNCS 6982: 81-92, 2011.
  14. Strategy-proof Mechanisms for Facility Location Games with Many Facilities, B. Escoffier, L. Gourvès, T. NGuyen Kim, F. Pascual and O. Spanjaard, ADT'11, LNCS 6992: 67-81,2011. Preliminary version.
  15. A Bottom-Up Method and Fast Algorithms for max independent set, N. Bourgeois, B. Escoffier, V. Th. Paschos and J.M.M Van Rooij, SWAT'10, LNCS 6139: 62-73, 2010
  16. Fast algorithms for min independent dominating set, N. Bourgeois, B. Escoffier and V. Th. Paschos, SIROCCO'10, LNCS 6058: 2-13, 2010
  17. On the impact of local taxes in a set cover game, B. Escoffier, L. Gourvès and J. Monnot, SIROCCO'10, LNCS 6058: 247-261, 2010
  18. Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n), N. Bourgeois, B. Escoffier, V. Th. Paschos and J.M.M Van Rooij, TAMC'10, LNCS 6108: 373-384, 2010
  19. Strategic Coloring of a Graph, B. Escoffier, L. Gourvès and J. Monnot, CIAC'10, LNCS 6078: 155-166, 2010
  20. Exact algorithms for dominating clique problems, N. Bourgeois, F. Della Croce, B. Escoffier and V. Th. Paschos, ISAAC'09, LNCS 5878: 4-13, 2009
  21. Efficient approximation of combinatorial problems by moderately exponential algorithms, N. Bourgeois, B. Escoffier and V. Th. Paschos, WADS'09, LNCS 5664: 507-518, 2009
  22. Single-Peaked consistency and its complexity, B. Escoffier, J. Lang and M. Öztürk, ECAI'08
  23. An O*(1.0977^n) exact algorithm for max independent set in sparse graphs, N. Bourgeois, B. Escoffier and V. Th. Paschos, IWPEC'08, LNCS 5018:55-65, 2008. Preliminary version.
  24. Some tractable instances of interval data minmax regret problems: bounded distance from triviality, B. Escoffier, J. Monnot and O. Spanjaard, SOFSEM'08, LNCS 4910: 280-291, 2008
  25. Adapting parallel algorithms to the W-Stream model, with applications to graph problems, C. Demetrescu, B. Escoffier, G. Moruz and A. Ribichini, MFCS'07, LNCS 4708: 194-205, 2007.
  26. Complexity and approximation results for the connected vertex cover problem, B. Escoffier, L. Gourvès and J. Monnot, WG'07, LNCS: 4769: 202-213, 2007
  27. Reoptimization of minimum and maximum traveling salesman's tour, G. Ausiello, B. Escoffier, J. Monnot and V. Th. Paschos, SWAT'06, LNCS 4059, 196-207, 2006. Preliminary version.
  28. Weighted Coloring: further complexity and approximations results, B. Escoffier, J. Monnot and V. Th. Paschos, ICTCS'05, LNCS 3701 : 205-214 (2005)
  29. Probabilistic Coloring of Bipartite and Split Graphs, F. Della Croce, B. Escoffier, C. Murat and V. Th. Paschos, ICCSA'05, LNCS 3483 : 202-211, 2005
  30. Differential Approximation of min sat, max sat and Related Problems, B. Escoffier and V. Th. Paschos, ICCSA'05, LNCS 3483 : 192-201, 2005
  31. Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation, D. de Werra, M. Demange, B. Escoffier J. Monnot and V. Th. Paschos, ISAAC'04, LNCS 3341, 896-907, 2004
  32. Poly-APX- and PTAS-completeness in standard and differential approximation, C. Bazgan, B. Escoffier and V. Th. Paschos, ISAAC'04, LNCS 3341, 124-136, 2004

Habilitation.

Models and algorithms in combinatorial optimization: some recent developments , Habilitation thesis, defended on Novembre, 2012.

PhD. Thesis

Approximation polynomiale : aspects structurels et opérationnels, PhD. thesis, defended on Novembre 4th, 2005. A summary of this thesis has been published in 4OR 5(2): 161-164 (2007).