Show simple item record

Asymptotic differential approximation ratio: definitions, motivations and an application to bin-packing

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-09T12:51:34Z
dc.date.available2010-01-09T12:51:34Z
dc.date.issued1999
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2845
dc.description.abstractfrWe 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.en
dc.language.isoenen
dc.subjectcoloringen
dc.subjectcoveringen
dc.subjectbin packingen
dc.subjectpolynomial time approximation algorithmen
dc.subjectcomplexityen
dc.subjectNP-complete problemen
dc.subject.ddc003en
dc.titleAsymptotic differential approximation ratio: definitions, motivations and an application to bin-packingen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversite Paris I, Paris;France
dc.description.abstractenNous commençons par définir et motiver une notion de rapport d'approximation différentiel 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.en
dc.relation.isversionofjnlnameRAIRO
dc.relation.isversionofjnlvol33en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate1999
dc.relation.isversionofjnlpages481-507en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherEDPen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record