Show simple item record

dc.contributor.authorBonnet, Edouard
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorStamoulis, Giorgios
dc.date.accessioned2020-07-22T13:08:21Z
dc.date.available2020-07-22T13:08:21Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20959
dc.language.isoenen
dc.subjectApproximation Guaranteeen
dc.subjectComputer-assisted Analysisen
dc.subjectSemiregular Bipartite Graphen
dc.subjectGeneralized Reduced Gradient (GRG)en
dc.subjectApproximation Ratioen
dc.subject.ddc005en
dc.titleA 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe study the polynomial time approximation of the max k-vertex cover problem in bipartite graphs and propose a purely combinatorial algorithm that beats the only such known algorithm, namely the greedy approach. We present a computer-assisted analysis of our algorithm, establishing that the worst case approximation guarantee is bounded below by 0.821.en
dc.identifier.citationpages235-248en
dc.relation.ispartoftitleLATIN 2016: Theoretical Informaticsen
dc.relation.ispartofeditorKranakis, Evangelos
dc.relation.ispartofeditorNavarro, Gonzalo
dc.relation.ispartofeditorChávez, Edgar
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofurl10.1007/978-3-662-49529-2en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-662-49529-2en
dc.relation.conftitle12th Latin American Theoretical Informatics Symposium (LATIN 2016)en
dc.relation.confdate2016-04
dc.relation.confcityEnsenadaen
dc.relation.confcountryMexicoen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-662-49529-2_18en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-07-22T12:57:28Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989
hal.person.labIds


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record