首页    期刊浏览 2025年02月18日 星期二
登录注册

文章基本信息

  • 标题:Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search
  • 本地全文:下载
  • 作者:Edward Hirsch
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2000
  • 卷号:2000
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:During the past three years there was an explosion of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order c^K, where c<2 is a constant, and K is the number of clauses in the input formula. Such bounds w.r.t. the number of variables instead of the number of clauses are not known. Also, it was proved that approximate solutions for these problems (even beyond inapproximability ratios) can be obtained faster than exact solutions. However, the corresponding exponents still depended on the number of clauses in the input formula. In this paper we give a randomized (1-\epsilon)-approximation algorithm for MAX-k-SAT. This algorithm runs in time of the order c_{k,\epsilon}^N, where N is the number of variables, and c_{k,\epsilon}<2 is a constant depending on k and \epsilon.
  • 关键词:Approximation Algorithms, Maximum Satisfiability, worst-case upper bounds
国家哲学社会科学文献中心版权所有