We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form 0 (2((1-mu(c))n)) for instances with n variables and m = cn clauses. In this setting, there are three incomparable currently best algorithms:...
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10389 485-496 2017年 [査読有り]
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg n − 1.4427n + O(log n). For many efficient algorithms, the first n lg n term is easy to achieve and our fo...
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E99A(6) 1019-1024 2016年6月 [査読有り]
We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in 2(1-Omega(1/log c))n time for instances with n variables and cn nodes.
大学本部
情報科学研究科