✦ LIBER ✦

An improved exponential-time algorithm for k -SAT

✍ Scribed by Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis

Book ID: 117995343
Publisher: Association for Computing Machinery
Year: 2005
Tongue: English
Weight: 222 KB
Volume: 52
Category: Article
ISSN: 0004-5411
DOI: 10.1145/1066100.1066101

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An improved deterministic local search a

An improved deterministic local search algorithm for 3-SAT

✍ Tobias Brueggemann; Walter Kern 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 222 KB

Exponential time improvement for min-wis

Exponential time improvement for min-wise based algorithms

✍ Guy Feigenblat; Ely Porat; Ariel Shiftan 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 284 KB

Improved Approximation Algorithms for MA

Improved Approximation Algorithms for MAX SAT

✍ Takao Asano; David P. Williamson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 215 KB

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze

A Better Algorithm for Random k -SAT

✍ Coja-Oghlan, Amin 📂 Article 📅 2010 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 499 KB

Improving exact algorithms for MAX-2-SAT

✍ Haiou Shen; Hantao Zhang 📂 Article 📅 2005 🏛 Springer Netherlands 🌐 English ⚖ 270 KB

An exact exponential time algorithm for

An exact exponential time algorithm for counting bipartite cliques

✍ Konstantin Kutzkov 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 152 KB