From: Eric Mahurin <eric.mahurin@...>
Date: 2008-06-14T03:35:50+09:00
Subject: Re: Preferable Pairs (#165)

------=_Part_7104_16650079.1213382185870
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 6/13/08, ThoML <micathom@gmail.com> wrote:
>
> Hi,
>
>
> > I found some interesting results with these extremes.  The love-hate case
> > allowed the ThomML algorithm to go up to hundreds of players (400 players
> in
> > 30seconds).  Probably O(n**2) or O(n**3) for this scenario.  The
> popularity
> > case was quite bad though - 14 players: 19s,  12 players: 1.8s, 10
> players:
> > 0.2s.  This looks to be O(n!).
>
>
> Thanks for the script for generating specific types of preferences.
> The performance depends on the adequacy of the underlying greedy
> algorithm for the data set. In the "love-hate" case, a simple greedy
> algorithm already returns optimal pairings. In the "popularity" case,
> such an approach doesn't work well.
>
> But the solution submitted is really simple and doesn't use too much
> memory. I experimented with memoizing subresults but came to the
> conclusion that it isn't worth the trouble for small random data sets
> because the cached data is hardly ever used. I assume memoization
> could help to avoid those variations you pointed out.


 I think to reasonably memoize in this problem and keep the memory low, you
need to represent each player as a bit.  With players<=31 (or <=63 for
64-bit machine), you can represent any set of players as a Fixnum.  A keys
in the memoize cache can a set of players (Fixnum) and the value can be the
optimal cost (also Fixnum).  With 28 players (30 seconds), my attempt only
uses 26MB.

Here are a few ideas to improve what you have further:

1. Represent each player as a bit.  Translate going in and out of the
algorithm.  This won't change the complexity, but should give a speedup of
several times because you are dealing with much simpler data (for the
computer).
2. Memoize costs.  This should change the worst case complexity from
factorial (squared?) to exponential (base 2).
3. Try a more accurate lower bound on the total cost.  Instead of cost*n/2,
you might try half of the sum of the next n costs.  Another possibility may
be to take half of the sum of the lowest remaining costs for each player.
These might not yield anything because the your current estimation is O(1)
and these are O(n).
4. Instead of sorting by simply pair cost, you might consider sorting by a
total estimated cost when a pair is chosen.  Not sure this will help since
it may be valid for the first pair chosen, but not necessarily good for ones
after that.
5. Instead of maintaining the current best pair sequence when finding the
lowest cost, this could be done in a separate lower complexity phase.  With
memoization this works well since you can easily use the costs in the cache
to "follow the crumbs".  Without, you may also be able to come up with some
marker scheme to retrace your steps.

The general scheme you are using is quite similar to the A* search
algorithm.  I also tried a more classic A* search on this problem, but
wasn't able to improve from what I had.  I think all of the extra overhead
needed wasn't paying off.

Eric

------=_Part_7104_16650079.1213382185870--