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 algorithm; satisfiability; stable roommates problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

90C27: Combinatorial optimization

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

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

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