Author |
Topic: Minimum-weight perfect matching (Read 8944 times) |
|
PMertens
Forum Guru
Arimaa player #692
Gender: 
Posts: 437
|
 |
Re: Algorithm Description #1
« Reply #15 on: Apr 18th, 2007, 6:27pm » |
 Quote  Modify
|
on Apr 17th, 2007, 2:34pm, Fritzlein wrote:
Wow, I didn't know I had any readers; I was just having fun writing. |
|
but you sure did know before that your stories have a decent fanbase ?
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Algorithm Description #1
« Reply #16 on: Apr 19th, 2007, 8:15am » |
Quote Modify
|
on Apr 18th, 2007, 4:30pm, BlackKnight wrote:| So the weights to be assigned to pairs might just be approximations. Do we really need a minimum weight perfect matching then, and how good is good enough? |
|
For 2006, we didn't try to find the global minimum, we used a form of greedy algorithm, namely to first assign the bye, then pair the top player, then pair the top unpaired player, etc. This caused serious problems in the computer championship by pairing too many repeat match-ups. That's why we switched to finding a global minimum in 2007.
Quote:| Maybe we could use an approximation algorithm. Even Greedy's performance is only twice as bad as the optimum. Those algorithms are much simpler to implement. |
|
The most obvious greedy algorithm can be arbitrarily bad, much more than twice as bad as optimal. Consider the following weights:
(A vs. B) = 1
(A vs. C) = 2
(A vs. D) = 3
(B vs. C) = 4
(B vs. D) = 5
(C vs. D) = 10,000
The greedy algorithm will first pair (A vs. B) and then have no choice but to pair (C vs. D).
The only approximation algorithm I have read relies on the triangle inequality to hold between the weights, and that is definitely not the case for us.
Quote:| Is there a link to the current pairing script? I only found a link to the pairing script for the postal. |
|
Paul Pogonyshev's branch-and-bound code for finding minimum-weight perfect matching is here:
on Jan 22nd, 2006, 1:31pm, doublep wrote:
However, his way of generating the weight matrix is not what we actually used for the 2007 World Championship, and for 2008 we probably want to use something different again. Also, for the first two rounds of 2007 the running time of doublep's code was intolerable (it is worst-case exponential) so we only used it from the third round onwards, i.e. after there had been some eliminations. Luckily, for the first two rounds we could use the 2006 greedy algorithm, because it happened to produce the same pairings as the global minimum for those rounds.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #17 on: Apr 19th, 2007, 4:02pm » |
Quote Modify
|
on Apr 19th, 2007, 8:15am, Fritzlein wrote:
The most obvious greedy algorithm can be arbitrarily bad, much more than twice as bad as optimal. |
|
This is of course absolutely right. I am sorry for jumping around in my last post. I was referring to maximum weight matching and to the 2-approximation for minimum weight matching of Goemans and Williamson. But you are right, this holds only under the triangle inequality.
And I guess my main concern was whether we should really (re-)implement 1000+ lines of code, if we can find a simple approximation algorithm.
But I wasn't aware of the fact, that it might be difficult to find one as I could only remember the two afore mentioned algorithms.
If there is no such algorithm, then maybe we can come up with one ... 
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #18 on: Apr 22nd, 2007, 4:04pm » |
Quote Modify
|
on Apr 19th, 2007, 8:15am, Fritzlein wrote:
Paul Pogonyshev's branch-and-bound code
Also, for the first two rounds of 2007 the running time of doublep's code was intolerable (it is worst-case exponential) so we only used it from the third round onwards, i.e. after there had been some eliminations. Luckily, for the first two rounds we could use the 2006 greedy algorithm, because it happened to produce the same pairings as the global minimum for those rounds. |
|
Thanks a lot for the link.
Do you still have the weight matrices for the first two rounds? I'd like to try them with the solver in Excel.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Algorithm Description #1
« Reply #19 on: Apr 22nd, 2007, 5:26pm » |
Quote Modify
|
on Apr 22nd, 2007, 4:04pm, BlackKnight wrote:| Do you still have the weight matrices for the first two rounds? I'd like to try them with the solver in Excel. |
|
I suggested a formula in the thread below...
on Sep 24th, 2006, 9:01pm, Fritzlein wrote:| To this end, let me rip apart the the eval function, and put it back together in the order of my priorities. |
|
and I think that is what omar eventually plugged into doublep's code. I think we should change the weight function again for next year, but that's another story.
I'll be extremely impressed if the Excel solver can do the job, given that it must either be framed as an integer program (paired=1, unpaired=0), or if you state it as a linear program, then the number of variables is exponential in the number of players.
|
| « Last Edit: Apr 22nd, 2007, 5:29pm by Fritzlein » |
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #20 on: Apr 22nd, 2007, 5:56pm » |
Quote Modify
|
on Apr 22nd, 2007, 5:26pm, Fritzlein wrote:
I'll be extremely impressed if the Excel solver can do the job, given that it must either be framed as an integer program (paired=1, unpaired=0), or if you state it as a linear program, then the number of variables is exponential in the number of players. |
|
Yes, 20 players is the maximum number of players we can pair. And this will not be enough in the future ... 
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Algorithm Description #1
« Reply #21 on: Apr 23rd, 2007, 3:01pm » |
Quote Modify
|
Quote:
... if we can find a simple approximation algorithm.
... it might be difficult to find one ... |
|
There was some recent (2003) research on simple approximation algorithms for maximum weighted matching.
But for minimum WM, the only thing I came across is a PhD thesis from 2000 with an implementation (free and Open Source(tm)) of the Lin-Kernighan heuristic for the Traveling Salesman Problem (TSP) and the minimum weight perfect matching problem.
It seems according to the experiments the weights of the matchings are about up to 2% over the optimum.
But it also takes more than five lines to implement ...
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Algorithm Description #1
« Reply #22 on: Apr 23rd, 2007, 3:53pm » |
Quote Modify
|
I confess, I'm not too excited about the idea of using an approximation algorithm. With an exact algorithm we can choose weights to guarantee principles such as, "No player can receive an Nth bye unless all remaining players have received their (N-1)st bye." Other parts of weighting may be approximate and disputable, but the bye rule should be ironclad. I also think it should be ironclad that a matching which repeats a pairing from a previous round can never be preferred over a matching without repeats, except if necessary to respect the bye rule.
I would hate to see a situation where one of these rules was violated unnecessarily, and we have to say, "Well, the whole pairing scheme is only approximate anyway." If it came to that, I would rather have a human tournament director do the pairings, and accept that the human would not find the optimal solution, but would have better judgment than a computer.
Not that I am volunteering to code up Edmonds' algorithm! It's just that I would rather have a human approximation than a computer approximation, if we couldn't be exact.
|
| « Last Edit: Apr 23rd, 2007, 3:53pm by Fritzlein » |
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Minimum-weight perfect matching
« Reply #23 on: Apr 23rd, 2007, 5:44pm » |
Quote Modify
|
And there might not be a simple approximation algorithm anyway?!
Jon Bentley: "Algorithm designers sleep peacefully only when they know their algorithms are the best possible;"
So, let's go for the optimum!
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Minimum-weight perfect matching
« Reply #24 on: Apr 25th, 2007, 12:43am » |
Quote Modify
|
How about using a solver at the NEOS server?
I just tried MINTO with a random instance of 32 players. The solver itself took 0.04 secs to find the minimum weight perfect matching.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #25 on: Apr 25th, 2007, 8:51am » |
Quote Modify
|
on Apr 25th, 2007, 12:43am, BlackKnight wrote:How about using a solver at the NEOS server?
I just tried MINTO with a random instance of 32 players. The solver itself took 0.04 secs to find the minimum weight perfect matching. |
|
Hey, wow! I didn't know there was a free, public solver that would do minimum weight perfect matching. I guess we can forget about implementing our own matching code, and start arguing appropriate weights instead!
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Minimum-weight perfect matching
« Reply #26 on: Feb 8th, 2010, 8:18pm » |
Quote Modify
|
I'm happy to report that our tractability problem is finally over and not just in theory. I found this page dedicated to the class of problems in question. From there it lead me to this virtual directory listing containing bare-bones code implementing Gabow's O(N^3) algorithm. It actually finds the maximum sum of weights and it's important that every weight is positive (not just non-negative) in order for all vertices to get paired. Here is the input and output corresponding to each of the above examples (format descriptions can be found in separate files):
Code:
4 6 U
3 0 0 0
2 621
3 676
4 101
3 0 0 0
1 621
3 686
4 1
3 0 0 0
1 676
2 686
4 201
3 0 0 0
1 101
2 1
3 201
|
|
Code:
Code:
6 15 U
5 0 0 0
2 508
3 509
4 454
5 452
6 1
5 0 0 0
1 508
3 505
4 457
5 5
6 454
5 0 0 0
1 509
2 505
4 9
5 457
6 456
5 0 0 0
1 454
2 457
3 9
5 509
6 510
5 0 0 0
1 452
2 5
3 457
4 509
6 508
5 0 0 0
1 1
2 454
3 456
4 510
5 508
|
|
Code:
Code:
6 15 U
5 0 0 0
2 1
3 1
4 1
5 1
6 100
5 0 0 0
1 1
3 1
4 1
5 100
6 1
5 0 0 0
1 1
2 1
4 100
5 1
6 1
5 0 0 0
1 1
2 1
3 100
5 1
6 1
5 0 0 0
1 1
2 100
3 1
4 1
6 1
5 0 0 0
1 100
2 1
3 1
4 1
5 1
|
|
Code:
It shouldn't be hard to figure out that it's working.
Now anyone can indulge himself in working out global rules for any tournament format.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #27 on: Feb 9th, 2010, 12:01am » |
Quote Modify
|
on Feb 8th, 2010, 8:18pm, aaaa wrote:| I'm happy to report that our tractability problem is finally over and not just in theory. |
|
Sweet! Now I can revive my campaign to eliminate the current preliminary/final dichotomy with a unified floating triple elimination. 
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Minimum-weight perfect matching
« Reply #28 on: Feb 10th, 2010, 6:58pm » |
Quote Modify
|
Awesome find aaaa. Now Karl can go wild with defining global rules for a floating elimination tournament
One of our main reasons for having a swiss preliminary was to provide a venue for players to take part in an organized tournament. Hopefully this year we will have more organized tournaments during the summer (like the Blitz tournament) so making the 2011 WC a FTE sounds possible. Although I would like it to still finish by the end of March (i.e. within 12 weeks).
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #29 on: Feb 10th, 2010, 7:59pm » |
Quote Modify
|
on Feb 10th, 2010, 6:58pm, omar wrote:Although I would like it to still finish by the end of March (i.e. within 12 weeks).
|
|
Given the same number of participants, floating triple elimination should actually finish faster than our current format. Our two problems with the format were not being able to handle a large crowd, and giving too much advantage to the top seed. If the size problem is now resolved, then all that remains is tweaking the pairing rules to be slightly more fair, i.e. slightly less dependent on pre-tournament ratings.
|
| « Last Edit: Feb 10th, 2010, 8:00pm by Fritzlein » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print