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-9743

Full text not available from this repository.

Abstract

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 [14]. 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
Publisher:	Springer
ISSN:	0302-9743
Book Title:	Automata, Languages and Programming
Date:	2011
Volume:	Vol.6755 (Automata, Languages and Programming)
Number of Pages:	12
Page Range:	pp. 305-316
Identification Number:	10.1007/978-3-642-22006-7_26
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/47710

Request changes to a record

Actions (login required)

View Item