A bounded approximation for the minimum cost 2-sat problem

DOI10.1007/BF01758838zbMath0753.68048MaRDI QIDQ1193517

Leonard Pitt, Dan Gusfield

Publication date: 27 September 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsatisfiabilitystable roommates problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (16)

On residual approximation in solution extension problems ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ On Residual Approximation in Solution Extension Problems ⋮ The stable roommates problem with short lists ⋮ The incremental satisfiability problem for a two conjunctive normal form ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification ⋮ Combining Traditional Map Labeling with Boundary Labeling ⋮ Using binary patterns for counting falsifying assignments of conjunctive forms ⋮ The Stable Roommates Problem with Short Lists ⋮ Hardness results for multimarginal optimal transport problems ⋮ Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights ⋮ On a cutting plane heuristic for the stable roommates problem and its applications ⋮ Network flow and 2-satisfiability ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalent approximation algorithms for node cover
• Structure preserving reductions among convex optimization problems
• Non deterministic polynomial optimization problems and their approximations
• An efficient algorithm for the “stable roommates” problem
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• A linear-time approximation algorithm for the weighted vertex cover problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures
• College Admissions and the Stability of Marriage

This page was built for publication: A bounded approximation for the minimum cost 2-sat problem