Show simple item record

A theorem on the approximation of set cover and vertex cover

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-03-22T09:54:17Z
dc.date.available2011-03-22T09:54:17Z
dc.date.issued1991
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5784
dc.language.isoenen
dc.subjectapproximation algorithmsen
dc.subjectVertex coveren
dc.subjectSet coveren
dc.subject.ddc003en
dc.titleA theorem on the approximation of set cover and vertex coveren
dc.typeCommunication / Conférence
dc.description.abstractenAn 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.en
dc.identifier.citationpages278-287en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriestitle560
dc.relation.ispartoftitleFoundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedingsen
dc.relation.ispartofeditorBiswas, Somenath
dc.relation.ispartofeditorNori, Kesav V.
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate1991
dc.relation.ispartofpages420en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/3-540-54967-6en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-54967-3en
dc.relation.conftitle11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91)en
dc.relation.confdate1991-12
dc.relation.confcityNew Delhien
dc.relation.confcountryIndeen
dc.identifier.doihttp://dx.doi.org/10.1007/3-540-54967-6_75


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record