On approximation hardness of the minimum 2SAT-DELETION problem

DOI10.1007/978-3-540-28629-5_18MaRDI QIDQ5311102zbMATH OpenOpenAlexFDO

Authors Miroslav Chlebík, Janka Chlebíková

Publication date 22 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99679, https://researchportal.port.ac.uk/portal/en/publications/on-approximation-hardness-of-the-minimum-2satdeletion-problem(767561a2-97f9-4a12-bd07-c7c220d57daf).html

zbMATH Keywords

approximation algorithmcombinatorial optimization problemsinapproximabilityNemhauser-Trotter Theoremperfect matchingsatisfiabilityvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• Approximating MIN 2-SAT and MIN 3-SAT
• On approximation algorithms for the minimum satisfiability problem
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• A polynomial time approximation scheme dense MIN 2SAT
• Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION
• A bounded approximation for the minimum cost 2-sat problem
• Approximating MIN k-SAT
• On the hardness of approximating the min-hack problem
• The complexity of minimal satisfiability problems

Cited in

(10)

• Affine reductions for LPs and SDPs
• On the complexity of minimum \(q\)-domination partization problems
• Solving \textsc{minones-2-sat} as fast as \textsc{vertex cover}
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Solving min ones 2-SAT as fast as vertex cover
• Approximation Algorithms for CSPs
• On approximating minimum vertex cover for graphs with perfect matching
• Approximation algorithm for minimum \(q\)-dominator partization problem
• On the counting version of the maximum 2-satisfiability problem
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover

This page was built for publication: On approximation hardness of the minimum 2SAT-DELETION problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311102)