Re:Capablanca: Minimum Vertex Cover Solver
by bicsi on Friday January 31, 2025 @02:58AM
(#42885538)
This is just BS.
If you follow their paper, their "inductive" argument can also prove that the result is optimal (the sqrt(2) constant is taken from thin air and may also be replaced by 1 without changing the proof).
My guess is that they tested some graphs, and "empirically" saw a bound of sqrt(2), and then came up with a proof to self-fulfill the profecy. They even mention that "for very small graphs, the approximation ratio may briefly exceed sqrt(2)", which is just nuts, given that they have a formal proof that it should never happen.
In case anyone read the paper and can't figure out the mistake in the proof, they assume that OPT_T + OPT_R = OPT, which is obviously false.
If you follow their paper, their "inductive" argument can also prove that the result is optimal (the sqrt(2) constant is taken from thin air and may also be replaced by 1 without changing the proof).
My guess is that they tested some graphs, and "empirically" saw a bound of sqrt(2), and then came up with a proof to self-fulfill the profecy. They even mention that "for very small graphs, the approximation ratio may briefly exceed sqrt(2)", which is just nuts, given that they have a formal proof that it should never happen.
In case anyone read the paper and can't figure out the mistake in the proof, they assume that OPT_T + OPT_R = OPT, which is obviously false.