Thumbnail - Request a copy

Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs

Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Georgios (2018), Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs, Discrete Optimization, 27, p. 26-56. 10.1016/j.disopt.2017.09.001

Type
Article accepté pour publication ou publié
Date
2018
Journal name
Discrete Optimization
Volume
27
Publisher
Elsevier
Pages
26-56
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, Georgios
Abstract (EN)
We study the polynomial time approximation of the NP-hard max -vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms. The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821.
Subjects / Keywords
Approximation algorithms; Combinatorial algorithms; Non linear program; Graph algorithms; Maximum coverage