Timeline for Calculating variance-minimal perfect matchings
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5 at 14:01 | comment | added | Max Alekseyev | @ClaudeChaunier: I see, thanks! For some reason I was thinking about variation rather than variance. Still, what I describe provides a heuristic (now indicated in the answer) that can do well for many practical instances. | |
| Jun 5 at 13:58 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
indicating heuristic
|
| Jun 5 at 9:10 | comment | added | Claude Chaunier | A perfect matching with edge weights $1, 3, 3, 3, 3, 3, 3, 3, 3, 5$ would have variance $8$ and $t - w = 4$, while a perfect matching with edge weights $2, 2, 2, 2, 2, 4, 4, 4, 4, 4$ would have variance $10$ and $t-w = 2$. As @BrendanMcKay hinted at, the minimum-range $t-w$ method would pick the second choice instead of the better first choice. | |
| Jun 4 at 9:55 | comment | added | Max Alekseyev | @ClaudeChaunier: I do not follow your point. Could you please elaborate? | |
| Jun 4 at 7:08 | comment | added | Claude Chaunier | I am afraid this is not going to help. The minimal variance might involve a minimal $w$ and a maximal $t$. | |
| Jun 3 at 11:01 | comment | added | Manfred Weis | that seems to be the only reasonable method... | |
| Jun 3 at 10:54 | history | answered | Max Alekseyev | CC BY-SA 4.0 |