As stated in this recent paper from ijcai https://www.ijcai.org/Proceedings/2019/0166.pdf

The top -Exact- algorithms worst case complexities are stated as follows enter image description here

where m is the number of clauses in the MaxSAT instance.

Why do MaxSAT algorithms (exact ones) scale exponentially as a function of m instead of n? Does this mean that these algorithms become worse than brute force ($O(m2^n)$) after m is a few multiples of n?

  • 1
    $\begingroup$ How about taking a look at one of these algorithms and seeing how it works? $\endgroup$ Jun 17 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.