Bruno Escoffier
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Bruno Escoffier has a total of 35 co-authors. Here are the top co-authors by number of shared publications:
- Jérôme Monnot
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
6 shared publications - Vangelis Th. Paschos
Université Paris-Dauphine
6 shared publications - Federico Della Croce
Dipartimento di Ingegneria Gestionale e della Produzione, Politecnico di Torino, 10129 Torino, Italy; and Consiglio Nazionale delle Ricerche, Istituto di elettronica e di ingegneria dell’informazione e delle telecomunicazioni, 10129 Torino, Italy
3 shared publications - Nicolas Bourgeois
Université Paris-Dauphine
3 shared publications Vangelis Th
LAMSADE Laboratoire d Analyses et Modélisation de Systèmes pour l Aide à la Décision UMR 7243 LAMSADE PSL Research University Université Paris-Dauphine CNRS UMR 7243
3 shared publicationsVangelis Th. Paschos
3 shared publications
Latest Publications
- Open Access
Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization
We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max k-vertex cover, k-densest subgraph, etc. By developing a technique "greediness-for-parameterization", we obtain fixed parameter algorithms with respect to a pair of parameters k, the size of the solution (but not its value) and \Delta, the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.
Open AccessMulti-parameter complexity analysis for constrained size graph problems: using greediness for parameterization
We study the parameterized complexity of a broad class of problems called "local graph partitioning problems" that includes the classical fixed cardinality problems as max k-vertex cover, k-densest subgraph, etc. By developing a technique "greediness-for-parameterization", we obtain fixed parameter algorithms with respect to a pair of parameters k, the size of the solution (but not its value) and \Delta, the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem.
- Open Access
Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between different approaches. In particular, whether Maximum Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this paper, we present a strong link between the linear PCP conjecture and the inapproximability, thus partially answering this question.
Open AccessSubexponential and FPT-time Inapproximability of Independent Set and Related Problems
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between different approaches. In particular, whether Maximum Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this paper, we present a strong link between the linear PCP conjecture and the inapproximability, thus partially answering this question.
- 1 November 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 459, 77-88
Algorithms for dominating clique problems
- 1 November 2012
- Published by Elsevier in Theoretical Computer Science
- Vol. 459, 77-88
Algorithms for dominating clique problems
- Open Access
Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between different approaches. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or fpt-time is a central question. In this paper, we present a strong link between the linear PCP conjecture and the inapproximability, thus partially answering this question.
Open AccessSubexponential and FPT-time Inapproximability of Independent Set and Related Problems
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between different approaches. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or fpt-time is a central question. In this paper, we present a strong link between the linear PCP conjecture and the inapproximability, thus partially answering this question.
- Open Access
- 1 January 2012
- Published by European Alliance for Innovation n.o.
Cost allocation protocols for network formation on connection situations
- 1 January 2012
- Published by European Alliance for Innovation n.o.
Open AccessCost allocation protocols for network formation on connection situations
- Open Access
Approximating MAX SAT by moderately exponential algorithms
We study approximation of the max sat problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to max sat in order to get approximation ratios arbitrarily close to 1.
Open AccessApproximating MAX SAT by moderately exponential algorithms
We study approximation of the max sat problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to max sat in order to get approximation ratios arbitrarily close to 1.
- Open Access
Minimum regulation of uncoordinated matchings
Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. A possible way to cope with selfishness is to compute a desired outcome (if it is tractable) and impose it. However this answer is often inappropriate because compelling an agent can be costly, unpopular or just hard to implement. Since both situations (no coordination and full coordination) show opposite advantages and drawbacks, it is natural to study possible tradeoffs. In this paper we study a strategic game where the nodes of a simple graph G are independent agents who try to form pairs: e.g. jobs and applicants, tennis players for a match, etc. In many instances of the game, a Nash equilibrium significantly deviates from a social optimum. We analyze a scenario where we fix the strategy of some players; the other players are free to make their choice. The goal is to compel a minimum number of players and guarantee that any possible equilibrium of the modified game is a social optimum, i.e. created pairs must form a maximum matching of G. We mainly show that this intriguing problem is NP-hard and propose an approximation algorithm with a constant ratio.
Open AccessMinimum regulation of uncoordinated matchings
Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. A possible way to cope with selfishness is to compute a desired outcome (if it is tractable) and impose it. However this answer is often inappropriate because compelling an agent can be costly, unpopular or just hard to implement. Since both situations (no coordination and full coordination) show opposite advantages and drawbacks, it is natural to study possible tradeoffs. In this paper we study a strategic game where the nodes of a simple graph G are independent agents who try to form pairs: e.g. jobs and applicants, tennis players for a match, etc. In many instances of the game, a Nash equilibrium significantly deviates from a social optimum. We analyze a scenario where we fix the strategy of some players; the other players are free to make their choice. The goal is to compel a minimum number of players and guarantee that any possible equilibrium of the modified game is a social optimum, i.e. created pairs must form a maximum matching of G. We mainly show that this intriguing problem is NP-hard and propose an approximation algorithm with a constant ratio.
- 25 October 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 411 (44-46) , 3994-4004
Adapting parallel algorithms to the W-Stream model, with applications to graph problems
- 25 October 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 411 (44-46) , 3994-4004
Adapting parallel algorithms to the W-Stream model, with applications to graph problems
- Open Access
- 19 October 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (1-2) , 382-415
Fast Algorithms for max independent set
- 19 October 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (1-2) , 382-415
Open AccessFast Algorithms for max independent set
- Open Access
Fast algorithms for min independent dominating set
We first devise a branching algorithm that computes a minimum independent dominating set on any graph with running time O*(2^0.424n) and polynomial space. This improves the O*(2^0.441n) result by (S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG'06). We then show that, for every r>3, it is possible to compute an r-((r-1)/r)log_2(r)-approximate solution for min independent dominating set within time O*(2^(nlog_2(r)/r)).
Open AccessFast algorithms for min independent dominating set
We first devise a branching algorithm that computes a minimum independent dominating set on any graph with running time O*(2^0.424n) and polynomial space. This improves the O*(2^0.441n) result by (S. Gaspers and M. Liedloff, A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG'06). We then show that, for every r>3, it is possible to compute an r-((r-1)/r)log_2(r)-approximate solution for min independent dominating set within time O*(2^(nlog_2(r)/r)).