About: Karloff–Zwick algorithm

An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

The Karloff–Zwick algorithm, in computational complexity theory, is a 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. and Uri Zwick presented the algorithm in 1997.

Property Value
dbo:abstract
  • The Karloff–Zwick algorithm, in computational complexity theory, is a 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. and Uri Zwick presented the algorithm in 1997. The algorithm is based on semidefinite programming. It can be derandomized using, e.g., the techniques from to yield a deterministic polynomial-time algorithm with the same approximation guarantees. (en)
dbo:wikiPageID
  • 3199764 (xsd:integer)
dbo:wikiPageLength
  • 3080 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1112157245 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • The Karloff–Zwick algorithm, in computational complexity theory, is a 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. and Uri Zwick presented the algorithm in 1997. (en)
rdfs:label
  • Karloff–Zwick algorithm (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License