A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs

Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios

Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios (2016), A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs, dans Kranakis, Evangelos; Navarro, Gonzalo; Chávez, Edgar, LATIN 2016: Theoretical Informatics, Springer, p. 235-248. 10.1007/978-3-662-49529-2_18

Voir/Ouvrir

Chapter_A0821-Ratio.pdf (293.0Kb)

Type

Communication / Conférence

Date

2016

Titre du colloque

12th Latin American Theoretical Informatics Symposium (LATIN 2016)

Date du colloque

2016-04

Ville du colloque

Ensenada

Pays du colloque

Mexico

Titre de l'ouvrage

LATIN 2016: Theoretical Informatics

Auteurs de l’ouvrage

Kranakis, Evangelos; Navarro, Gonzalo; Chávez, Edgar

Éditeur

Springer

Isbn

978-3-662-49529-2

Pages

235-248

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Stamoulis, Giorgios

Résumé (EN)

We 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.

Mots-clés

Approximation Guarantee; Computer-assisted Analysis; Semiregular Bipartite Graph; Generalized Reduced Gradient (GRG); Approximation Ratio