Revision as of 14:27, 10 February 2019 edit Citation bot (talk \| contribs) Bots 5,861,692 edits m Alter: title. Add: citeseerx, isbn, chapter. \| You can use this bot yourself. Report bugs here. \| User-activated. ← Previous edit		Revision as of 18:05, 10 February 2019 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,585 edits Clean up after the Bot broke a template Next edit →
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 performs equally well on arbitrary 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?\|~~work~~title-link= ~~Proc. 38th Annual [[~~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}}.</ref> ==Comparison to random assignment==

Karloff–Zwick algorithm: Difference between revisions