Show simple item record

Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBonnet, Edouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis
hal.structure.identifier
dc.contributor.authorStamoulis, Georgios
dc.date.accessioned2020-07-22T10:20:59Z
dc.date.available2020-07-22T10:20:59Z
dc.date.issued2018
dc.identifier.issn1572-5286
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20955
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectCombinatorial algorithmsen
dc.subjectNon linear programen
dc.subjectGraph algorithmsen
dc.subjectMaximum coverageen
dc.subject.ddc005en
dc.titlePurely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study the polynomial time approximation of the NP-hard max -vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms. The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821.en
dc.relation.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol27en
dc.relation.isversionofjnldate2018-02
dc.relation.isversionofjnlpages26-56en
dc.relation.isversionofdoi10.1016/j.disopt.2017.09.001en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-07-22T10:17:34Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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