Simple approximation algorithms for balanced MAX~2SAT

DOI10.1007/s00453-017-0312-6zbMath1390.68766OpenAlexW2488011622MaRDI QIDQ1742374

Alice Paul, David P. Williamson, Matthias Poloczek

Publication date: 11 April 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0312-6

zbMATH Keywords

approximation algorithmgreedy algorithmspectral algorithmmaximum satisfiabilitybalanced instancespriority algorithm

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Simpler 3/4-Approximation Algorithms for MAX SAT
• Towards Sharp Inapproximability for Any 2-CSP
• Bounds on Greedy Algorithms for MAX SAT
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max Cut and the Smallest Eigenvalue
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• On Some Recent Approximation Algorithms for MAX SAT
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?