The decimation process in random k-SAT
Coja-Oghlan, Amin and Pachon-Pinzon, Angelica Y.. (2011) The decimation process in random k-SAT. Lecture Notes in Computer Science, Vol.6755 (Automata, Languages and Programming) . pp. 305-316. ISSN 0302-9743Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-22006-7_26
Let k be an even integer. We investigate the applicability of approximation techniques to the problem of deciding whether a random k-SAT formula is satisfiable. Let n be the number of propositional variables under consideration. First we show that if the number m of clauses satisfies m≥ Cn k/2 for a certain constant C, then unsatisfiability can be certified efficiently using (known) approximation algorithms for MAX CUT or MIN BISECTION. In addition, we present an algorithm based on the Lovász ϑ function that within polynomial expected time decides whether the input formula is satisfiable, provided m≥ Cn k/2. These results improve previous work by Goerdt and Krivelevich . Finally, we present an algorithm that approximates random MAX 2-SAT within expected polynomial time.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Lecture Notes in Computer Science|
|Book Title:||Automata, Languages and Programming|
|Volume:||Vol.6755 (Automata, Languages and Programming)|
|Number of Pages:||12|
|Page Range:||pp. 305-316|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)