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
2018Journal name
Discrete OptimizationVolume
27Publisher
Elsevier
Pages
26-56
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, Edouard
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 coverageRelated items
Showing items related by title and author.
-
Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios (2016) Communication / Conférence
-
Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2015) Article accepté pour publication ou publié
-
Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié