Content deleted Content added
Citation bot (talk | contribs) Alter: journal. Add: isbn, s2cid. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
Citation bot (talk | contribs) Alter: title. Add: chapter. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1065/2306 |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
The '''Karloff–Zwick algorithm''', in [[computational complexity theory]], is a [[randomized algorithm|randomised]] [[approximation algorithm]] taking an instance of [[MAX-3SAT]] [[Boolean satisfiability problem]] as input. If the instance is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. There is strong evidence (but not a [[mathematical proof]]) that the algorithm achieves 7/8 of optimal even on unsatisfiable MAX-3SAT instances. [[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref name="Karloff">{{citation|last1=Karloff|first1= H.|title= Proceedings 38th Annual Symposium on Foundations of Computer Science|last2= Zwick|first2= U. |chapter=A 7/8-approximation algorithm for MAX 3SAT?|title-link=Symposium on Foundations of Computer Science|year=1997|pages=406–415|doi=10.1109/SFCS.1997.646129|isbn= 978-0-8186-8197-4|citeseerx= 10.1.1.51.1351|s2cid= 15447333}}.</ref>
The algorithm is based on [[semidefinite programming]]. It can be derandomized using, e.g., the techniques from <ref>{{citation|last1=Sivakumar |first1=D. |title
==Comparison to random assignment==
| |||