Show simple item record

Differential approximation algorithms for some combinatorial optimization problems

dc.contributor.authorDemange, Marc
dc.contributor.authorGrisoni, Pascal
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-12T14:22:31Z
dc.date.available2010-01-12T14:22:31Z
dc.date.issued1998
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2901
dc.language.isoenen
dc.subjectSet coveringen
dc.subjectBin-packingen
dc.subjectColoringen
dc.subjectPolynomial time approximation algorithmen
dc.subjectNP-complete problemen
dc.subject.ddc003en
dc.titleDifferential approximation algorithms for some combinatorial optimization problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe use a new approximation measure, the differential approximation ratio, to derive polynomial-time approximation algorithms for minimum set covering (for both weighted and unweighted cases), minimum graph coloring and bin-packing. We also propose differential-approximation-ratio preserving reductions linking minimum coloring, minimum vertex covering by cliques, minimum edge covering by cliques and minimum edge covering of a bipartite graph by complete bipartite graphs.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol209en
dc.relation.isversionofjnlissue1-2en
dc.relation.isversionofjnldate1998-12
dc.relation.isversionofjnlpages107-122en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0304-3975(97)00099-6en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
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