6
$\begingroup$

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ What does TIA stand for? $\endgroup$
    – Rodrigo de Azevedo
    Aug 21, 2021 at 7:54
  • 3
    $\begingroup$ @RodrigodeAzevedo Probably “thanks in advance”. $\endgroup$
    – Emil Jeřábek
    Aug 21, 2021 at 21:53
  • 4
    $\begingroup$ I'm not sure why someone downvoted this; I think it's a good question. As far as I know, the answer is "yes." We sort of used $2^{\omega n/3}$ being optimal for solving MAX-CUT as a hardness assumption in work from a few years ago. $\endgroup$
    – Huck Bennett
    Aug 21, 2021 at 22:30
  • 2
    $\begingroup$ Yes, this is still the best known algorithm for the Max-CUT problem on graphs of unbounded average degree. For graphs of small average degree (say, <=10 or so), faster algorithms exist. $\endgroup$
    – Alex Golovnev
    Aug 24, 2021 at 19:37
  • 3
    $\begingroup$ @OmarShehab, here're two examples, but I'm not sure if these are the best known algorithms for Max-CUT in sparse graphs: sciencedirect.com/science/article/pii/S0167637706000587 and golovnev.org/papers/max2sat.pdf $\endgroup$
    – Alex Golovnev
    Aug 26, 2021 at 14:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.