Simple approximation algorithms for balanced MAX~2SAT
type: Item
instance of: scholarly article
title: Simple approximation algorithms for balanced MAX~2SAT
zbMATH Open document ID: 1390.68766
author: Alice Paul
author: Matthias Poloczek
author: David P. Williamson
published in: Algorithmica
publication date: 2018-04-11T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 6858537
zbMATH Keywords: maximum satisfiability
zbMATH Keywords: approximation algorithm
zbMATH Keywords: greedy algorithm
zbMATH Keywords: spectral algorithm
zbMATH Keywords: balanced instances
zbMATH Keywords: priority algorithm
MaRDI profile type: Publication
full work available at URL: s00453-017-0312-6
OpenAlex ID: W2488011622
cites work: Q3604010
cites work: Towards Sharp Inapproximability for Any 2-CSP
cites work: A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Approximation algorithms for combinatorial problems
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Q4737518
cites work: Q4780789
cites work: Bounds on Greedy Algorithms for MAX SAT
cites work: Q5365070
cites work: Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
cites work: On the Approximation of Maximum Satisfiability
cites work: On Some Recent Approximation Algorithms for MAX SAT
cites work: Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
cites work: Max Cut and the Smallest Eigenvalue
cites work: Simpler 3/4-Approximation Algorithms for MAX SAT
DOI: 10.1007/S00453-017-0312-6
description: scientific article; zbMATH DE number 6858537