Mathemalsky
commented
2 years ago The code is fine.
About the test: I am not sure whether the test makes sense. So if I understood correctly the optimal value is around 12 so you count the times it was at least half that. However, this means that it would be valid for the algorithm to be below half the optimum in the most cases as long as it is above half the optimum in the expected value. Hence I don't think this counting makes any sense. I would say that simply computing the average and comparing that one is a better choice even though that one may fail in some rare cases.
Yes you are right in that point. Another problem is also. That for the actual test it is imposible to get a solution below half of the optimal value, because the clauses are long enough.
Besides that I think it would be possible to improve the amsyptotic runtime by using an unordered map instead of the vector of pairs in my actual findVariable function.
Approximation algorithm for the unbiased maximum satisfaction problem. Due to the randomness there is no canonical appropriate test.