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, 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

Chapter_A0821-Ratio.pdf (293.0Kb)

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

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