An improved algorithm for the (n,3)documentclass12pt{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$(n, 3)$$end{document}-MaxSAT problem: asking branchings to satisfy the clauses

摘要

Abstract We study the (n,3)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$(n, 3)$$end{document}-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n,3)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$(n, 3)$$end{document}-MaxSAT problem which significantly improves the previous results. More precisely, the running time of our algorithm can be bounded by O∗(1.175k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$O^*(1.175^k)$$end{document} and O∗(1.194n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$O^*(1.194^n)$$end{document}, respectively. Prior to our study, the running time of the best known exact algorithm can be bounded by O∗(1.194k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$O^*(1.194^k)$$end{document} and O∗(1.237n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$O^*(1.237^n)$$end{document}, respectively.