MDMarc Demange

Marc Demange

*This is an algorithmically generated author record based on publicly available information.

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


Marc Demange has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems

    by Marc Demange, Vangelis Th. Paschos

    We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing, the “first fit decreasing”. Next we deal with minimum vertex-covering-by-cliques of a graph and the minimum edge-covering-by-complete-bipartite-subgraphs of a bipartite graph and devise a differential-approximation preserving reduction from the former to the latter. Finally, we prove two negative differential approximation results about the ability of minimum vertex-coloring to be approximated by a polynomial time approximation schema. Nous commençons par définir et motiver une notion de rapport d'approximation dif fé ren tiel asymptotique. Pour cela, nous introduisons une classe de problèmes que nous appelons radiaux qui comprend en particulier les problèmes héréditaires. Puis nous validons la définition de rapport d'approximation différentiel asymptotique en établissant des résultats positifs, conditionnels et négatifs pour différents problèmes combinatoires. Nous proposons d'abord une analyse, dans le cadre de l'approximation différentielle, d'un algorithme glouton classique (le first fit decreasing ) pour le problème de bin packing. Nous traitons alors les problèmes de couverture minimum des sommets d'un graphe par des cliques induites et des arêtes d'un graphe biparti par des sous-graphes partiels bipartis complets et donnons une réduction préservant l'approximation différentielle du premier au second. Enfin, nous prouvons deux résultats négatifs concernant la possibilité d'approcher le problème de coloration des sommets d'un graphe par un schéma d'approximation différentiel polynomial.


  • Approximation results for the minimum graph coloring problem

    by Marc Demange, Pascal Grisoni, Vangelis Th. Paschos