• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
10.1016/j.disopt.2017.09.001
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

Related items

Showing items related by title and author.

  • Thumbnail
    A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs 
    Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios (2016) Communication / Conférence
  • Thumbnail
    Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems 
    Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Thumbnail
    Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization 
    Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2015) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo