A new algorithm for MAX-2-SAT

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

25 Цитирования (Scopus)

Аннотация

Recently there was a significant progress in proving (exponential- time) worst-case upper bounds for the propositional satisfiability problem (SAT) and related problems. In particular, for MAX-2-SAT Niedermeier and Rossmanith recently presented an algorithm with worstcase upper bound O(K·2K/2:88…), and the bound O(K·2K/3:44..) is implicit from the paper by Bansal and Raman (K is the number of clauses). In this paper we improve this bound to p(K)2K2/4, where K2 is the number of 2-clauses, and p is a polynomial. In addition, our algorithm and the proof are much simpler than the previous ones. The key ideas are to use the symmetric flow algorithm of Yannakakis and to count only 2-clauses (and not 1-clauses).

Язык оригиналаанглийский
Название основной публикацииSTACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings
РедакторыHorst Reichel, Sophie Tison
ИздательSpringer Nature
Страницы65-73
Число страниц9
ISBN (печатное издание)9783540671411
СостояниеОпубликовано - 1 янв 2000
Событие17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 - Lille, Франция
Продолжительность: 17 фев 200019 фев 2000

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

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

Конференция

Конференция17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000
СтранаФранция
ГородLille
Период17/02/0019/02/00

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

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

Fingerprint Подробные сведения о темах исследования «A new algorithm for MAX-2-SAT». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Hirsch, E. A. (2000). A new algorithm for MAX-2-SAT. В H. Reichel, & S. Tison (Ред.), STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings (стр. 65-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 1770). Springer Nature.