Simple approximation algorithms for balanced MAX~2SAT
From MaRDI portal
Publication:1742374
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
approximation algorithmgreedy algorithmspectral algorithmmaximum satisfiabilitybalanced instancespriority algorithm
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?