DOI

We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O*(1.358k). This improves the bound O*(1.370k) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.

Original languageEnglish
Title of host publicationParameterized and Exact Computation - 7th International Symposium, IPEC 2012, Proceedings
Pages37-48
Number of pages12
DOIs
StatePublished - 1 Dec 2012
Event7th International Symposium on Parameterized and Exact Computation, IPEC 2012 - Ljubljana, Slovenia
Duration: 12 Sep 2013 → 14 Sep 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7535 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Symposium on Parameterized and Exact Computation, IPEC 2012
Country/TerritorySlovenia
CityLjubljana
Period12/09/13 → 14/09/13

    Research areas

  • exact algorithms, maximum satisfiability, parameterized algorithms, satisfiability

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 49788154