Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-27T13:58:45Z
dc.date.available2010-04-27T13:58:45Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4016
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectExponential algorithmsen
dc.subject.ddc003en
dc.titleApproximation by Moderately Exponential Algorithmsen
dc.typeCommunication / Conférence
dc.description.abstractenWe present a trade-off between polynomial approximation and exact computation. We show how using ideas from both fields one can design approximation algorithms for several combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We then show how such ratios can be achieved for maximum independent set, minimum vertex cover and minimum set cover.en
dc.relation.ispartoftitleCombinatorial Optimization ISCO2010. Recent Progress
dc.relation.ispartofeditorMahjoub, Ali Ridha
dc.relation.ispartofpublnameWiley
dc.relation.ispartofpublcityLondon
dc.relation.ispartofdate2011
dc.relation.ispartofpages416
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn9781848212060
dc.relation.conftitleISCO International Symposium on Combinatorial Optimizationen
dc.relation.confdate2010-03
dc.relation.confcityHammameten
dc.relation.confcountryTunisieen


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