### Abstract

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·2^{K/2:88…}), and the bound O(K·2^{K/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)2^{K2/4}, where K_{2} 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).

Original language | English |
---|---|

Title of host publication | STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings |

Editors | Horst Reichel, Sophie Tison |

Publisher | Springer Nature |

Pages | 65-73 |

Number of pages | 9 |

ISBN (Print) | 9783540671411 |

Publication status | Published - 1 Jan 2000 |

Event | 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 - Lille Duration: 17 Feb 2000 → 19 Feb 2000 |

### Publication series

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

Volume | 1770 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000 |
---|---|

Country | France |

City | Lille |

Period | 17/02/00 → 19/02/00 |

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'A new algorithm for MAX-2-SAT'. Together they form a unique fingerprint.

## Cite this

*STACS 2000 - 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, Proceedings*(pp. 65-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1770). Springer Nature.