Issue |
RAIRO-Oper. Res.
Volume 33, Number 4, October-December 1999
|
|
---|---|---|
Page(s) | 481 - 507 | |
DOI | https://doi.org/10.1051/ro:1999121 | |
Published online | 15 August 2002 |
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
1
CERMSEM, Universite Paris I,
106-112 boulevard de l'Hôpital, 75647 Paris Cedex 13, France.
2
LAMSADE, Universite Paris-Dauphine,
Place du Marechal de Lattre de Tassigny, 75775
Paris Cedex 16, France.
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.
Résumé
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.
Key words: NP-complete problem / complexity / polynomial time approximation algorithm / bin packing / coloring / covering.
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.