Standard

A new algorithm for parameterized MAX-SAT. / Bliznets, Ivan; Golovnev, Alexander.

Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings. 2012. p. 37-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7535 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Bliznets, I & Golovnev, A 2012, A new algorithm for parameterized MAX-SAT. in Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7535 LNCS, pp. 37-48, 7th International Symposium on Parameterized and Exact Computation, IPEC 2012, Ljubljana, Slovenia, 12/09/13. https://doi.org/10.1007/978-3-642-33293-7_6

APA

Bliznets, I., & Golovnev, A. (2012). A new algorithm for parameterized MAX-SAT. In Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings (pp. 37-48). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7535 LNCS). https://doi.org/10.1007/978-3-642-33293-7_6

Vancouver

Bliznets I, Golovnev A. A new algorithm for parameterized MAX-SAT. In Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings. 2012. p. 37-48. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-33293-7_6

Author

Bliznets, Ivan ; Golovnev, Alexander. / A new algorithm for parameterized MAX-SAT. Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings. 2012. pp. 37-48 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1afa7518b91e47598ad6819779ec6b95,
title = "A new algorithm for parameterized MAX-SAT",
abstract = "We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O*(1.358k). This improves the bound O*(1.370k) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.",
keywords = "exact algorithms, maximum satisfiability, parameterized algorithms, satisfiability",
author = "Ivan Bliznets and Alexander Golovnev",
year = "2012",
month = dec,
day = "1",
doi = "10.1007/978-3-642-33293-7_6",
language = "English",
isbn = "9783642332920",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "37--48",
booktitle = "Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings",
note = "7th International Symposium on Parameterized and Exact Computation, IPEC 2012 ; Conference date: 12-09-2013 Through 14-09-2013",

}

RIS

TY - GEN

T1 - A new algorithm for parameterized MAX-SAT

AU - Bliznets, Ivan

AU - Golovnev, Alexander

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O*(1.358k). This improves the bound O*(1.370k) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.

AB - We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O*(1.358k). This improves the bound O*(1.370k) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.

KW - exact algorithms

KW - maximum satisfiability

KW - parameterized algorithms

KW - satisfiability

UR - http://www.scopus.com/inward/record.url?scp=84873445257&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33293-7_6

DO - 10.1007/978-3-642-33293-7_6

M3 - Conference contribution

AN - SCOPUS:84873445257

SN - 9783642332920

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 37

EP - 48

BT - Parameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings

T2 - 7th International Symposium on Parameterized and Exact Computation, IPEC 2012

Y2 - 12 September 2013 through 14 September 2013

ER -

ID: 49788154