ESCOFFIER Bruno
Full Professor
Team :
RO
Localisation :
Campus Pierre et Marie Curie Sorbonne Université - LIP6 Tel: +33 1 44 27 72 09, Bruno.Escoffier (at)
null lip6.fr
https://webia.lip6.fr/~escoffier
2 PhD students (Supervision / Co-supervision)
2004-2019 Publications
All
Books
Journal articles
Book chapters
Conference papers
Other publications
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 ”, 27th 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 ”, 44th 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 - 17th 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 ”, 16th 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
2016
B. Escoffier : “Saving colors and Max Coloring: some fixed-parameter tractability results ”, Proceedings of WG 2016, 42nd 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 - 12th 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
2013
B. Escoffier, J. Monnot, F. Pascual, O. Spanjaard : “Truthful many-to-many assignment with private weights ”, 8th 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 ”, 14e 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, K. Eun Jung, 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 ”, 2nd 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 ”, 12e 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
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) ”, 34th 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 ”, 18th 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)
LIP6 » News
Full Professor
