In this paper we present a new randomized algorithm for SAT combining unit clause elimination and local search. The algorithm is inspired by two randomized algorithms having the best current worst-case upper bounds ([9] and [11,12]). Despite its simplicity, our algorithm performs well on many common benchmarks (we present results of its empirical evaluation). It is also probabilistically approximately complete.

Язык оригиналаанглийский
Название основной публикацииPrinciples and Practice of Constraint Programming - CP 2001 - 7th International Conference, CP 2001, Proceedings
РедакторыToby Walsh
ИздательSpringer Nature
Страницы605-609
Число страниц5
ISBN (печатное издание)3540428631, 9783540428633
СостояниеОпубликовано - 1 янв 2001
Событие7th International Conference on Principles and Practice of Constraint Programming, CP 2001 - Paphos, Кипр
Продолжительность: 26 ноя 20011 дек 2001

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том2239
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция7th International Conference on Principles and Practice of Constraint Programming, CP 2001
Страна/TерриторияКипр
ГородPaphos
Период26/11/011/12/01

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49829404