Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT

by: Amin Coja-Oghlan, Andreas Goerdt, Andre Lanka, Frank Schadlich

Theoretical Computer Science, Vol. 329, No. 1-3. (13 December 2004), pp. 1-45.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

johannsen

Find related articles with these CiteULike tags

Abstract

We apply techniques from the theory of approximation algorithms to the problem of deciding whether a random k-SAT formula is satisfiable. Let Formn,k,m denote a random k-SAT instance with n variables and m clauses. Using known approximation algorithms for MAX CUT or MIN BISECTION, we show how to certify that Formn,4,m is unsatisfiable efficiently, provided that m[greater-or-equal, slanted]Cn2 for a sufficiently large constant C>0. In addition, we present an algorithm based on the Lovasz [theta] function that decides within polynomial expected time whether Formn,k,m is satisfiable, provided that k is even and m[greater-or-equal, slanted]C[middle dot]4knk/2. Finally, we present an algorithm that approximates random MAX 2-SAT on input Formn,2,m within a factor of 1-O(n/m)1/2 in expected polynomial time, for m[greater-or-equal, slanted]Cn.

@article{citeulike:139140, abstract = {We apply techniques from the theory of approximation algorithms to the problem of deciding whether a random k-SAT formula is satisfiable. Let Formn,k,m denote a random k-SAT instance with n variables and m clauses. Using known approximation algorithms for MAX CUT or MIN BISECTION, we show how to certify that Formn,4,m is unsatisfiable efficiently, provided that m[greater-or-equal, slanted]Cn2 for a sufficiently large constant C>0. In addition, we present an algorithm based on the Lovasz [theta] function that decides within polynomial expected time whether Formn,k,m is satisfiable, provided that k is even and m[greater-or-equal, slanted]C[middle dot]4knk/2. Finally, we present an algorithm that approximates random MAX 2-SAT on input Formn,2,m within a factor of 1-O(n/m)1/2 in expected polynomial time, for m[greater-or-equal, slanted]Cn.}, author = {Coja-Oghlan, Amin and Goerdt, Andreas and Lanka, Andre and Schadlich, Frank }, citeulike-article-id = {139140}, doi = {10.1016/j.tcs.2004.07.017}, journal = {Theoretical Computer Science}, keywords = {sat}, month = {December}, number = {1-3}, pages = {1--45}, posted-at = {2005-03-24 15:09:12}, priority = {2}, title = {Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT}, url = {http://dx.doi.org/10.1016/j.tcs.2004.07.017}, volume = {329}, year = {2004} }

RIS record

TY - JOUR ID - citeulike:139140 L3 - citeulike-article-id:139140 TI - Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT JF - Theoretical Computer Science VL - 329 IS - 1-3 SP - 1 EP - 45 N2 - We apply techniques from the theory of approximation algorithms to the problem of deciding whether a random k-SAT formula is satisfiable. Let Formn,k,m denote a random k-SAT instance with n variables and m clauses. Using known approximation algorithms for MAX CUT or MIN BISECTION, we show how to certify that Formn,4,m is unsatisfiable efficiently, provided that m[greater-or-equal, slanted]Cn2 for a sufficiently large constant C>0. In addition, we present an algorithm based on the Lovasz [theta] function that decides within polynomial expected time whether Formn,k,m is satisfiable, provided that k is even and m[greater-or-equal, slanted]C[middle dot]4knk/2. Finally, we present an algorithm that approximates random MAX 2-SAT on input Formn,2,m within a factor of 1-O(n/m)1/2 in expected polynomial time, for m[greater-or-equal, slanted]Cn. KW - sat AU - Coja-Oghlan, Amin AU - Goerdt, Andreas AU - Lanka, Andre AU - Schadlich, Frank PY - 2004/12/13/ UR - http://dx.doi.org/10.1016/j.tcs.2004.07.017 ER -

RIS BibTeX