Paper Info
Title
Simple Approximation Algorithms for Balanced MAX 2SAT
Abstract
We study simple algorithms for the balanced MAX 2SAT problem, where we are given weighted clauses of length one and two with the property that for each variable  the total weight of clauses that  appears in equals the total weight of clauses for . We show that such instances have a simple structural property in that any optimal solution can satisfy at most the total weight of the clauses minus half the total weight of the unit clauses. Using this property and a novel analysis of the computation tree, we are able to show that a large class of greedy algorithms, including Johnson’s algorithm, gives a -approximation algorithm for balanced MAX 2SAT; a similar statement is false for general MAX 2SAT instances. We further give a spectral 0.81-approximation algorithm for balanced MAX E2SAT instances (in which each clause has exactly 2 literals) by a reduction to a spectral algorithm of Trevisan for the maximum colored cut problem. We provide experimental results showing that this spectral algorithm performs well and is slightly better than Johnson’s algorithm and the Goemans–Williamson semidefinite programming algorithm on balanced MAX E2SAT instances.
Year
DOI
Venue
2016
https://doi.org/10.1007/s00453-017-0312-6
Algorithmica
Keywords
Field
DocType
Maximum satisfiability,Approximation algorithm,Greedy algorithm,Spectral algorithm,Balanced instances,Priority algorithm
Discrete mathematics,Approximation algorithm,Combinatorics,Colored,Structural property,Greedy algorithm,Overline,SIMPLE algorithm,Computation tree,Semidefinite programming,Mathematics
Conference
Volume
Issue
ISSN
80
3
0178-4617
Citations 
PageRank 
References 
0
0.34
10
Authors
3
Name
Order
Citations
PageRank
Alice Paul100.34
Matthias Poloczek2536.39
David P. Williamson33564413.34