Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 фев 2000 → 19 фев 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 |
---|---|
Страна/Tерритория | Франция |
Город | Lille |
Период | 17/02/00 → 19/02/00 |
ID: 49829759