Show simple item record

A 0.821-Ratio Purely Combinatorial Algorithm 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, 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.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Chapter_A0821-Ratio.pdf
Size:
293.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record