2013

Articles

• Escoffier, Bruno ; Gourvès, Laurent ; Monnot, Jérôme . Fair solutions for some multiagent optimization problems. Autonomous Agents and Multi-Agent Systems. Volume 26. n° 2. 2013. pages 184-201. Springer. DOI http://dx.doi.org/10.1007/s10458-011-9188-z.

2012

Articles

• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas ; Van Rooij, Johan . Fast Algorithms for max independent set. Algorithmica. Volume 62. n° 1-2. 2012. pages 382-415. Springer. DOI http://dx.doi.org/10.1007/s00453-010-9460-7.

Working Papers

• Escoffier, Bruno ; Kim, Eun Jung ; Paschos, Vangelis . Subexponential and FPT-time Inapproximability of Independent Set and Related Problems. Université Paris-Dauphine . 2012 .

2011

Articles

• Moruz, Gabriel ; Escoffier, Bruno ; Demetrescu, Camil ; Ribichini, Andrea . Adapting parallel algorithms to the W-Stream model, with applications to graph problems. Theoretical Computer Science. Volume 411. n° 44-46. 2011. pages 3994-4004. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2010.08.030.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Applied Mathematics. Volume 159. n° 17. 2011. pages 1954-1970. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2011.07.009.

Book chapters

• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas . An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems. Mahjoub, Ridha. Progress in Combinatorial Optimization: Recent Progress. . 2011. pages chapter 15.

Conference Contributions

• Escoffier, Bruno ; Bonifaci, Vicenzo ; Ausiello, Giorgio . Complexity and Approximation in Reoptimization. CiE 2007: Logic and Computation and Logic in the Real World. Sienne. Italie. 2007.
• Spanjaard, Olivier ; Pascual, Fanny ; Nguyen, Thang Kim ; Gourvès, Laurent ; Escoffier, Bruno . Algorithmes à véracité garantie pour le placement d'installations sur une ligne. 12e congrès annuel de la Société française de Recherche Opérationnelle et d’Aide à la Décision. Saint Etienne. France. 2011.
• Spanjaard, Olivier ; Pascual, Fanny ; Thang, Nguyen Kim ; Gourvès, Laurent ; Escoffier, Bruno . Strategy-Proof Mechanisms for Facility Location Games with Many Facilities. ADT 2011. Piscataway. États-Unis. 2011.

Working Papers

• Escoffier, Bruno ; Paschos, Vangelis ; Tourniaire, Emeric . Approximating MAX SAT by moderately exponential algorithms. Université Paris-Dauphine . 2011 .
• Boria, Nicolas ; Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Exponential approximation schemata for some network design problems. Université Paris-Dauphine . 2011 .

2010

Articles

• Monnot, Jérôme ; Gourvès, Laurent ; Escoffier, Bruno . Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs. Journal of Discrete Algorithms. Volume 8. n° 1. 2010. pages 36-49. Elsevier. DOI http://dx.doi.org/10.1016/j.jda.2009.01.005.
• Gourvès, Laurent ; Escoffier, Bruno ; Spanjaard, Olivier ; Monnot, Jérôme . Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation. European Journal of Operational Research. Volume 205. n° 1. 2010. pages 19-30. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2009.12.004.
• Paschos, Vangelis ; Escoffier, Bruno . A Survey on the Structure of Approximation Classes. Computer Science Review. Volume 4. n° 1. 2010. pages 19-40. Elsevier. DOI http://dx.doi.org/10.1016/j.cosrev.2009.11.001.

Conference Contributions

• Monnot, Jérôme ; Gourvès, Laurent ; Escoffier, Bruno . On the impact of local taxes in a set cover game. Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.. Sirince. Turquie. 2010.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . A Bottom-Up Method and Fast Algorithms for max independent set. 12th Scandinavian Symposium and Workshops on Algorithm Theory - SWAT'10. Bergen. Norvège. 2010.
• Van Rooij, Johan ; Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n). Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings. Berlin. République tchèque. 2010.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Fast Algorithms for min independent dominating set. SIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity. Sirince. Turquie. 2010.
• Bourgeois, Nicolas ; Della Croce, Federico ; Escoffier, Bruno ; Paschos, Vangelis . Exact Algorithms for Dominating Clique Problems. ISAAC 2009 20th International Symposium on Algorithms and Computation. Hawaï. États-Unis. 2009.
• Escoffier, Bruno ; Gourvès, Laurent ; Monnot, Jérôme . Strategic Coloring of a Graph. Algorithms and Complexity 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings. Rome. Italie. 2010.

2009

Articles

• Paschos, Vangelis ; Escoffier, Bruno ; Milanic, Martin . Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research. Volume 4. n° 2. 2009. pages 86-94. Preeminent Academic Facets Inc..
• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas . Efficient approximation of MIN SET COVER by moderately exponential algorithms. Theoretical Computer Science. Volume 410. n° 21-23. 2009. pages 2184-2195. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2009.02.007.
• Ausiello, Giorgio ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of minimum and maximum traveling salesman's tours. Journal of Discrete Algorithms. Volume 7. n° 4. 2009. pages 453-463. Elsevier. DOI http://dx.doi.org/10.1016/j.jda.2008.12.001.
• Murat, Cécile ; Escoffier, Bruno ; Della Croce, Federico ; Bourgeois, Nicolas ; Paschos, Vangelis . Probabilistic graph-coloring in bipartite and split graphs. Journal of Combinatorial Optimization. Volume 17. n° 3. 2009. pages 274-311. Springer Netherlands. DOI http://dx.doi.org/10.1007/s10878-007-9112-2.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Approximation of MIN COLORING by moderately exponential algorithms. Information Processing Letters. Volume 109. n° 16. 2009. pages 950-954. Elsevier. DOI http://dx.doi.org/10.1016/j.ipl.2009.05.002.
• Paschos, Vangelis ; Monnot, Jérôme ; Escoffier, Bruno ; Demange, Marc ; de Werra, Dominique . Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discrete Applied Mathematics. Volume 157. n° 4. 2009. pages 819-832. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2008.06.013.

Conference Contributions

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms. 11th International Symposium on Algorithms and Data Structures (WADS'09). Banff. Canada. 2009.

2008

Articles

• Escoffier, Bruno ; Monnot, Jérôme . Better differential approximation for symmetric TSP. Theoretical Computer Science. Volume 396. n° 1-3. 2008. pages 63-70. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2008.01.002.
• Escoffier, Bruno ; Monnot, Jérôme ; Spanjaard, Olivier . Some tractable instances of interval data minmax regret problems. Operations Research Letters. Volume 36. n° 4. 2008. pages 424-429. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2007.12.004.

Book chapters

• Della Croce, Federico ; Escoffier, Bruno ; Kaminski, Marcin ; Paschos, Vangelis . Worst-case complexity of exact algorithms for NP-hard problems. Paschos, Vangelis. Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE. Hoboken NJ. 2008. pages 203-240.
• Escoffier, Bruno ; Demange, Marc ; de Werra, Dominique ; Milis, Ioannis ; Lucarelli, Giorgio ; Paschos, Vangelis ; Monnot, Jérôme . Weighted edge coloring. Paschos, Vangelis. Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE. Hoboken NJ. 2008. pages 291-318.
• Escoffier, Bruno ; Demange, Marc ; Paschos, Vangelis ; de Werra, Dominique ; Monnot, Jérôme . Complexity and approximation results for the min weighted node coloring problem. Paschos, Vangelis. Combinatorial optimization and theoretical computer science: interfaces and perspectives. . 2008. pages 251-280.

Conference Contributions

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs. Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008). Victoria. Canada. 2008.
• Escoffier, Bruno ; Monnot, Jérôme ; Spanjaard, Olivier . Some tractable instances of interval data minmax regret problems: bounded distance from triviality. SOFSEM 2008: Theory and Practice of Computer Science 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings. Nový Smokovec. Slovaquie. 2008.
• Oztürk, Meltem ; Lang, Jérôme ; Escoffier, Bruno . Quelques aspects algorithmiques du raisonnement sur les préférences unimodales. RFIA 2008 : 16e congrès francophone AFRIF-AFIA Reconnaissance des Formes et Intelligence Artificielle. Amiens. France. 2008.
• Lang, Jérôme ; Escoffier, Bruno ; Oztürk, Meltem . Single-Peaked Consistency and its Complexity. ECAI 2008 - 18th European Conference on Artificial Intelligence. Patras. Grèce. 2008.

Working Papers

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Efficient approximation by “low-complexity” exponential algorithms. Université Paris-Dauphine . 2008 .
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis ; van Rooij, Johan . Fast algorithms for Max Independant Set in graphs of small average degree. Université Paris-Dauphine . 2008 .

2007

Articles

• Paschos, Vangelis ; Della Croce, Federico ; Escoffier, Bruno . Improved worst-case complexity for the MIN 3-SET COVERING problem. Operations Research Letters. Volume 35. n° 2. 2007. pages 205-210. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2006.02.004.
• Paschos, Vangelis ; Escoffier, Bruno . Differential approximation of MIN SAT, MAX SAT and related problems. European Journal of Operational Research. Volume 181. n° 2. 2007. pages 620-633. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2005.04.057.
• Escoffier, Bruno ; Hammer, Peter . Approximation of the Quadratic Set Covering Problem. Discrete Optimization. Volume 4. n° 3-4. 2007. pages 378-386. Elsevier. DOI http://dx.doi.org/10.1016/j.disopt.2007.10.001.

Conference Contributions

• Ribichini, Andrea ; Moruz, Gabriel ; Escoffier, Bruno ; Demetrescu, Camil . Adapting parallel algorithms to the W-Stream model, with applications to graph problems. 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07). Berlin. République tchèque. 2007.
• Escoffier, Bruno ; Gourvès, Laurent ; Monnot, Jérôme . Complexity and approximation results for the connected vertex cover problem. WG'07 33rd International Workshop on Graph-Theoretic Concepts in Computer Science. Dornburg. Allemagne. 2007.

Working Papers

• Escoffier, Bruno ; Paschos, Vangelis . Structures des classes d'approximation : un état de l'art. Université Paris-Dauphine . 2007 .

2006

Articles

• Paschos, Vangelis ; Escoffier, Bruno . On-line models and algorithms for max independent set. RAIRO Operations Research. Volume 40. n° 2. 2006. pages 129-142. EDP Sciences. DOI http://dx.doi.org/10.1051/ro:2006014.
• Paschos, Vangelis ; Escoffier, Bruno ; Monnot, Jérôme . Weighted coloring: further complexity and approximability results. Information Processing Letters. Volume 97. n° 3. 2006. pages 98-103. Elsevier. DOI http://dx.doi.org/10.1016/j.ipl.2005.09.013.
• Paschos, Vangelis ; Escoffier, Bruno . Completeness in approximation classes beyond APX. Theoretical Computer Science. Volume 359. n° 1-3. 2006. pages 369-377. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2006.05.023.

Conference Contributions

• Ausiello, Giorgio ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of minimum and maximum traveling salesman's tours. 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Berlin. Lettonie. 2006.

Working Papers

• Demetrescu, Camil ; Escoffier, Bruno ; Moruz, Gabriel ; Ribichini, Andrea . Parallel Algorithms are Good for Streaming. Université Paris-Dauphine . 2006 .

2005

Articles

• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theoretical Computer Science. Volume 339. n° 2-3. 2005. pages 272-292. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2005.03.007.
• Escoffier, Bruno ; Paschos, Vangelis . Proving completeness by logic. International Journal of Computer Mathematics. Volume 82. n° 2. 2005. pages 151-161. Taylor & Francis. DOI http://dx.doi.org/10.1080/00207160412331296625.

Book chapters

• Escoffier, Bruno ; Spanjaard, Olivier . Programmation dynamique. V. Th. Paschos. Optimisation Combinatoire 1 : concepts fondamentaux. Paris. 2005.

Conference Contributions

• Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Weighted coloring: further complexity and approximability results. 9th Italian Conference on Theoretical Computer Science (ICTCS'05). Berlin. Italie. 2005.
• Escoffier, Bruno ; Paschos, Vangelis . Differential approximation of MIN SAT, MAX SAT and related problems. International Conference on Computational Science and Its Applications (ICCSA'05). Berlin. Singapour. 2005.
• Della Croce, Federico ; Escoffier, Bruno ; Murat, Cécile ; Paschos, Vangelis . Probabilistic coloring of bipartite and split graphs. International Conference on Computational Science and Its Applications (ICCSA'05). Singapour. Singapour. 2005.

2004

Conference Contributions

• de Werra, Dominique ; Demange, Marc ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation. Algorithms and Computation 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. Berlin. Chine. 2004.
• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Poly-APX- and PTAS-completeness in standard and differential approximation. ISAAC'04 :15th International Symposium. Hong Kong. Chine. 2004.

Working Papers

• Escoffier, Bruno ; Paschos, Vangelis . An Alternative proof of SAT NP-Completeness. Université Paris-Dauphine . 2004 .