Thumbnail

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

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

View/Open
Type
Communication / Conférence
Date
2016
Conference title
12th Latin American Theoretical Informatics Symposium (LATIN 2016)
Conference date
2016-04
Conference city
Ensenada
Conference country
Mexico
Book title
LATIN 2016: Theoretical Informatics
Book author
Kranakis, Evangelos; Navarro, Gonzalo; Chávez, Edgar
Publisher
Springer
ISBN
978-3-662-49529-2
Pages
235-248
Publication identifier
Metadata
Show full item record
Author(s)
Bonnet, Edouard cc
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
Abstract (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.
Subjects / Keywords
Approximation Guarantee; Computer-assisted Analysis; Semiregular Bipartite Graph; Generalized Reduced Gradient (GRG); Approximation Ratio