Show simple item record

Differential approximation for satisfiability and related problems

dc.contributor.authorBazgan, Cristina
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-12T14:09:08Z
dc.date.available2009-10-12T14:09:08Z
dc.date.issued2003
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2213
dc.language.isoenen
dc.subjectComplexity theory
dc.subjectHeuristics
dc.subjectCombinatorial optimization
dc.subject.ddc511en
dc.titleDifferential approximation for satisfiability and related problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study the differential approximability of several optimization satisfiability problems. We prove that, unless co−RP=NP, MIN SAT is not differential 1/m1−var epsilon-approximable for any var epsilon>0, where m is the number of clauses. We also prove that any differential approximation algorithm for MAX minimal vertex cover can be transformed into a differential approximation algorithm for MIN kSAT achieving the same differential performance ratio. This leads us to study the differential approximability of MAX minimal vertex cover and MIN independent dominating set. Both of them are equivalent for the differential approximation. For these problems we prove a strong inapproximability result, informally, unless P=NP, any approximation algorithm has worst-case approximation ratio equal to 0.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol147
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2003
dc.relation.isversionofjnlpages397-404
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0377-2217(02)00299-0
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:49:19Z


Files in this item

Thumbnail
Name:
publi143.pdf
Size:
274.1Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record