Standard
New bounds for MAX-SAT by glause learning. / Kulikov, Alexander S.; Kutzkov, Konstantin.
Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. 2007. p. 194-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4649 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Harvard
Kulikov, AS & Kutzkov, K 2007,
New bounds for MAX-SAT by glause learning. in
Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4649 LNCS, pp. 194-204, 2nd International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russian Federation,
3/09/07.
APA
Kulikov, A. S., & Kutzkov, K. (2007).
New bounds for MAX-SAT by glause learning. In
Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings (pp. 194-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4649 LNCS).
Vancouver
Kulikov AS, Kutzkov K.
New bounds for MAX-SAT by glause learning. In Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. 2007. p. 194-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Author
Kulikov, Alexander S. ; Kutzkov, Konstantin. /
New bounds for MAX-SAT by glause learning. Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. 2007. pp. 194-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{efd8d8c3138f4feeabc4e34496f7921a,
title = "New bounds for MAX-SAT by glause learning",
abstract = "To solve a problem on a given CNF formula F a splitting algorithm recursively calls for F[v] and F[¬v] for a variable v. Obviously, after the first call an algorithm obtains some information on the structure of the formula that can be used in the second call. We use this idea to design new surprisingly simple algorithms for the MAX-SAT problem. Namely, we show that MAX-SAT for formulas with constant clause density can be solved in time c n, where c < 2 is a constant and n is the number of variables, and within polynomial space (the only known such algorithm by Dantsin and Wolpert uses exponential space). We also prove that MAX-2-SAT can be solved in time 2m/5.88, where m is the number of clauses (this improves the bound 2m/5,769 proved independently by Kneis et al. and by Scott and Sorkin).",
author = "Kulikov, {Alexander S.} and Konstantin Kutzkov",
year = "2007",
month = dec,
day = "24",
language = "English",
isbn = "9783540745099",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "194--204",
booktitle = "Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings",
note = "2nd International Symposium on Computer Science in Russia, CSR 2007 ; Conference date: 03-09-2007 Through 07-09-2007",
}
RIS
TY - GEN
T1 - New bounds for MAX-SAT by glause learning
AU - Kulikov, Alexander S.
AU - Kutzkov, Konstantin
PY - 2007/12/24
Y1 - 2007/12/24
N2 - To solve a problem on a given CNF formula F a splitting algorithm recursively calls for F[v] and F[¬v] for a variable v. Obviously, after the first call an algorithm obtains some information on the structure of the formula that can be used in the second call. We use this idea to design new surprisingly simple algorithms for the MAX-SAT problem. Namely, we show that MAX-SAT for formulas with constant clause density can be solved in time c n, where c < 2 is a constant and n is the number of variables, and within polynomial space (the only known such algorithm by Dantsin and Wolpert uses exponential space). We also prove that MAX-2-SAT can be solved in time 2m/5.88, where m is the number of clauses (this improves the bound 2m/5,769 proved independently by Kneis et al. and by Scott and Sorkin).
AB - To solve a problem on a given CNF formula F a splitting algorithm recursively calls for F[v] and F[¬v] for a variable v. Obviously, after the first call an algorithm obtains some information on the structure of the formula that can be used in the second call. We use this idea to design new surprisingly simple algorithms for the MAX-SAT problem. Namely, we show that MAX-SAT for formulas with constant clause density can be solved in time c n, where c < 2 is a constant and n is the number of variables, and within polynomial space (the only known such algorithm by Dantsin and Wolpert uses exponential space). We also prove that MAX-2-SAT can be solved in time 2m/5.88, where m is the number of clauses (this improves the bound 2m/5,769 proved independently by Kneis et al. and by Scott and Sorkin).
UR - http://www.scopus.com/inward/record.url?scp=37249068927&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:37249068927
SN - 9783540745099
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 194
EP - 204
BT - Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings
T2 - 2nd International Symposium on Computer Science in Russia, CSR 2007
Y2 - 3 September 2007 through 7 September 2007
ER -
