Standard

Local search algorithms for SAT : Worst-case analysis. / Hirsch, Edward A.

Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Stefan Arnborg; Lars Ivansson. Springer Nature, 1998. p. 246-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1432).

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

Harvard

Hirsch, EA 1998, Local search algorithms for SAT: Worst-case analysis. in S Arnborg & L Ivansson (eds), Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1432, Springer Nature, pp. 246-254, 6th Scandinavian Workshop on Algorithm Theory, SWAT 1998, Stockholm, Sweden, 8/07/98. https://doi.org/10.1007/BFb0054372

APA

Hirsch, E. A. (1998). Local search algorithms for SAT: Worst-case analysis. In S. Arnborg, & L. Ivansson (Eds.), Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 246-254). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1432). Springer Nature. https://doi.org/10.1007/BFb0054372

Vancouver

Hirsch EA. Local search algorithms for SAT: Worst-case analysis. In Arnborg S, Ivansson L, editors, Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Nature. 1998. p. 246-254. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/BFb0054372

Author

Hirsch, Edward A. / Local search algorithms for SAT : Worst-case analysis. Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Stefan Arnborg ; Lars Ivansson. Springer Nature, 1998. pp. 246-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{903d4217fff94a998d46e8c6de042bfd,
title = "Local search algorithms for SAT: Worst-case analysis",
abstract = "Recent experiments demonstrated that local search algorithms (e.g. GSAT) are able to find satisfying assignments for many {"}hard{"} Boolean formulas. However, no non-trivial worst-case upper bounds were proved, although many such bounds of the form 2αn (α < 1 is a constant) are known for other SAT algorithms, e.g. resolution-like algorithms. In the present paper we prove such a bound for a local search algorithm, namely for CSAT. The class of formulas we consider covers most of DIMACS benchmarks, the satisfiability problem for this class of formulas is NP-complete.",
author = "Hirsch, {Edward A.}",
year = "1998",
month = jan,
day = "1",
doi = "10.1007/BFb0054372",
language = "English",
isbn = "3540646825",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "246--254",
editor = "Stefan Arnborg and Lars Ivansson",
booktitle = "Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings",
address = "Germany",
note = "6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 ; Conference date: 08-07-1998 Through 10-07-1998",

}

RIS

TY - GEN

T1 - Local search algorithms for SAT

T2 - 6th Scandinavian Workshop on Algorithm Theory, SWAT 1998

AU - Hirsch, Edward A.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - Recent experiments demonstrated that local search algorithms (e.g. GSAT) are able to find satisfying assignments for many "hard" Boolean formulas. However, no non-trivial worst-case upper bounds were proved, although many such bounds of the form 2αn (α < 1 is a constant) are known for other SAT algorithms, e.g. resolution-like algorithms. In the present paper we prove such a bound for a local search algorithm, namely for CSAT. The class of formulas we consider covers most of DIMACS benchmarks, the satisfiability problem for this class of formulas is NP-complete.

AB - Recent experiments demonstrated that local search algorithms (e.g. GSAT) are able to find satisfying assignments for many "hard" Boolean formulas. However, no non-trivial worst-case upper bounds were proved, although many such bounds of the form 2αn (α < 1 is a constant) are known for other SAT algorithms, e.g. resolution-like algorithms. In the present paper we prove such a bound for a local search algorithm, namely for CSAT. The class of formulas we consider covers most of DIMACS benchmarks, the satisfiability problem for this class of formulas is NP-complete.

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

U2 - 10.1007/BFb0054372

DO - 10.1007/BFb0054372

M3 - Conference contribution

AN - SCOPUS:84957711442

SN - 3540646825

SN - 9783540646822

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

SP - 246

EP - 254

BT - Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Arnborg, Stefan

A2 - Ivansson, Lars

PB - Springer Nature

Y2 - 8 July 1998 through 10 July 1998

ER -

ID: 49830053