kactl icon indicating copy to clipboard operation
kactl copied to clipboard

General Matching has unnecessary factor of 8

Open ecnerwala opened this issue 4 years ago • 0 comments

In the randomized General Matching code, the code only knows how to extract a perfect matching, so we add up to N additional vertices before computing the matrix inverse which blows runtime up by a factor of 8. This is unnecessary, you can instead just restrict the set of vertices to the basis found in the first run of Gaussian elimination. You also shouldn't need to run Gaussian elimination a second time. (See https://codeforces.com/blog/entry/92400). This would require rewriting matInv's interface a little.

ecnerwala avatar Dec 24 '21 20:12 ecnerwala