Differential approximation for satisfiability and related problems
Bazgan, Cristina; Paschos, Vangelis (2003), Differential approximation for satisfiability and related problems, European Journal of Operational Research, 147, 2, p. 397-404. http://dx.doi.org/10.1016/S0377-2217(02)00299-0
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (EN)We 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.
Subjects / KeywordsComplexity theory; Heuristics; Combinatorial optimization
Showing items related by title and author.
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é
Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2005) Article accepté pour publication ou publié