Combinatorial approximation of maximum k -vertex cover in bipartite graphs within ratio 0.7

Paschos, Vangelis Th.

Paschos, Vangelis Th. (2018), Combinatorial approximation of maximum k -vertex cover in bipartite graphs within ratio 0.7, RAIRO - Operations Research, 52, 1, p. 305-314. 10.1051/ro/2017085

Type

Article accepté pour publication ou publié

External document link

https://arxiv.org/abs/1502.07930

Date

2018

Journal name

RAIRO - Operations Research

Volume

Number

Publisher

EDP Sciences

Pages

305-314

Publication identifier

10.1051/ro/2017085

Metadata

Show full item record

Author(s)

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

Abstract (EN)

We propose and analyze a simple purely combinatorial algorithm for MAX K-VERTEX COVER in bipartite graphs, achieving approximation ratio 0.7. The only combinatorial algorithm currently known until now for this problem is the natural greedy algorithm, that achieves ratio (e − 1)/e = 0.632.

Subjects / Keywords

Approximation algorithm; Bipartite graph; Max k-VERTEX cover