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

Edouard Bonnet, Bruno Escoffier, Vangelis Paschos, Georgios Stamoulis*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We study the polynomial time approximation of the NP-hard MAX k-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. We also study two simpler strategies with provable approximation ratios of 2/3 and 34/47 approximate to 0.72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio (1-1/e) approximate to 0.632. Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for MAX k-VERTEX COVEr compete with linear programming ones? (C) 2017 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)26-56
Number of pages31
JournalDiscrete Optimization
Volume27
DOIs
Publication statusPublished - 1 Feb 2018

Keywords

  • Approximation algorithms
  • Combinatorial algorithms
  • Graph algorithms
  • MAX-CUT
  • Maximum coverage
  • Non linear program

Cite this