Demange Marc

Marc Demange

Information about the author Marc Demange will soon be added to the site.
Found 10 papers in total
Asymptotic differential approximation ratio:Definitions, motivations and application to some combinatorial problems
Asymptotic differential approximation ratio:Definitions, motivations and application to some combinatorial problems
1999
We first motivate and define a notion of asymptotic differential approximation ratio....
On-line maximum-order induced hereditary subgraph problems
On-line maximum-order induced hereditary subgraph problems
2005
We first study the competitive ratio for the on-line version of the problem of finding...
Polynomial approximation algorithms with performance guarantees: An introduction-by-example
Polynomial approximation algorithms with performance guarantees: An introduction-by-example
2005
We present a short overview on polynomial approximation of NP-hard problems. We...
A unified formulation and approach to the analysis of approximation algorithms: the structure of NP optimisation problems
A unified formulation and approach to the analysis of approximation algorithms: the structure of NP optimisation problems
2002
This paper is the continuation of the paper “Autour de nouvelles notions pour...
A unified formulation and approach to the analysis of approximation algorithms
A unified formulation and approach to the analysis of approximation algorithms
2002
The main objective of the polynomial approximation is the development of polynomial...
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
1999
We first motivate and define a notion of asymptotic differential approximation ratio....
Reducing off-line to on-line: an example and its applications
Reducing off-line to on-line: an example and its applications
2003
We study on-line versions of maximum weighted hereditary subgraph problems for which...
Reducing off-line to on-line: An example and its applications
Reducing off-line to on-line: An example and its applications
2003
We study on-line versions of maximum weighted hereditary subgraph problems for which...
A generalization of König–Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
A generalization of König–Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
1997
We first study a generalization of the König–Egervary graphs, the class of...
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
1997
We prove that the existence of a polynomial time ρ-approximation algorithm (where...
Papers per page: