Chlebík, Miroslav and Chlebíková, Janka (2004) On approximation hardness of the minimum 2SAT-deletion problem. In: 29th International Symposium on Mathematical Foundations of Computer Science, Prague, CZECH REPUBLIC.

Full text not available from this repository.

Abstract

The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems [8], and its approximability is largely open. We prove a lower approximation bound of 8root5 - 15 approximate to 2.88854, improving the previous bound of 10root5 - 21 approximate to 1.36067 by Dinur and Safra [5]. For highly restricted instances with exactly 4 occurrences of every variable we provide a lower bound of 3/2. Both inapproximability results apply to instances with no mixed Clauses (the literals in every clause are both either negated, or unnegated). We further prove that any k-approximation algorithm for MINIMUM 2SAT-DELETION polynomially reduces to a (2 - 2/k+1)-approximation algorithm for the MINIMUM VERTEX COVER problem. One ingredient of these improvements is our proof that for the MINIMUM VERTEX COVER problem restricted to graphs with a perfect matching its threshold on polynomial time approximability is the same as for the general MINIMUM VERTEX COVER problem. This improves also on results of Chen and Kanj [3].

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	Mathematical Foundations of Computer Science 2004
Schools and Departments:	School of Mathematical and Physical Sciences > Mathematics
Depositing User:	Miroslav Chlebik
Date Deposited:	06 Feb 2012 19:08
Last Modified:	11 Apr 2012 11:45
URI:	http://sro.sussex.ac.uk/id/eprint/19378

📧 Request an update