Differential approximation for satisfiability and related problems
Cristina Bazgan, Vangélis Th. Paschos · Base Institutionnelle de Recherche de l'université Paris-Dauphine (BIRD) (University Paris-Dauphine) · 2003
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.