Show simple item record

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2012-04-24T14:41:33Z
dc.date.available2012-04-24T14:41:33Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9038
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectExponential time algorithmsen
dc.subjectMaximum independent seten
dc.subjectMinimum vertex coveren
dc.subject.ddc003en
dc.titleApproximation of max independent set, min vertex cover and related problems by moderately exponential algorithmsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
dc.description.abstractenUsing ideas and results from polynomial time approximation and exact computation we design approximationalgorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, maxindependentset and minvertexcover.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol159en
dc.relation.isversionofjnlissue17en
dc.relation.isversionofjnldate2011
dc.relation.isversionofjnlpages1954-1970en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2011.07.009en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
mod_exp_approx.pdf
Size:
328.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record