Approximating a generalization of MAX 2SAT and MIN 2SAT

DOI10.1016/S0166-218X(00)00244-4zbMath0971.68070WikidataQ127956999 ScholiaQ127956999MaRDI QIDQ1841882

Anu Pathria, Dorit S. Hochbaum

Publication date: 30 October 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

2SAT problemsgenclauses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

A primal-dual approximation algorithm for \textsc{minsat} ⋮ Classes of linear programs solvable by coordinate-wise minimization ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

Cites Work

• Unnamed Item
• Unnamed Item
• On the Complexity of Timetable and Multicommodity Flow Problems
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

This page was built for publication: Approximating a generalization of MAX 2SAT and MIN 2SAT