Content deleted Content added
Siddharthist (talk | contribs) Add section on weighted MAX-SAT, including an ILP, the relaxed LP, and two approximation algorithms from Vazirani |
Siddharthist (talk | contribs) →Weighted MAX-SAT: Add another reference for the weighted MAX-SAT definition |
||
Line 14:
== Weighted MAX-SAT ==
More generally, one can define a weighted version of MAX-SAT as follows: given a conjunctive normal form formula with non-negative weights assigned to each clause, find truth values for its variables that maximize the combined weight of the satisfied clauses. The MAX-SAT problem is an instance of weighted MAX-SAT where all weights are 1.{{sfn|Vazirani|2001|p=131}}<ref>{{Cite journal|last=Borchers|first=Brian|last2=Furman|first2=Judith|date=1998-12-01|title=A Two-Phase Exact Algorithm for MAX-SAT and Weighted MAX-SAT Problems|url=https://link.springer.com/article/10.1023/A:1009725216438|journal=Journal of Combinatorial Optimization|language=en|volume=2|issue=4|pages=299–306|doi=10.1023/A:1009725216438|issn=1382-6905}}</ref>
=== Approximation algorithms ===
| |||