A theorem on the approximation of set cover and vertex cover

Thumbnail
Date
1991
Titre de la collection
Lecture Notes in Computer Science560
Indexation documentaire
Recherche opérationnelle
Subject
approximation algorithms; Vertex cover; Set cover
Réf version publiée
http://dx.doi.org/10.1007/3-540-54967-6_75
Titre du colloque
11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)
Date du colloque
12-1991
Ville du colloque
New Delhi
Pays du colloque
Inde
Titre de l'ouvrage
Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedings
Auteur
Biswas, Somenath; Nori, Kesav V.
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin
Année
1991
Nombre total de pages
420
ISBN
978-3-540-54967-3
URL de l'ouvrage
http://dx.doi.org/10.1007/3-540-54967-6
URI
https://basepub.dauphine.fr/handle/123456789/5784
Collections
Métadonnées
Afficher la notice complète
Auteur
Paschos, Vangelis
Type
Communication / Conférence
Nombre de pages du document
278-287
Résumé en anglais
An approximation result is given, connecting two well known combinatorial problems, the Set Cover and the Vertex Cover. This result constitutes an improvement of the existing ratio for the latter, on a large and intuitive class of graphs, provided that an approximation algorithm exists for the former.