Higher order Hungarian algorithm?

Say I have 3 vectors that may have different lengths. For example:

a=[ 4  5   2];
b=[-8 -13  3];
c=[ 4  7  -9  11];

How do I find the associations (if any) so that the sum of one element from each vector is:

1. Minimized.
2. Below a certain threshold (let's say 2 in this example).

Note that once an association is made, those values are removed.

So in this case, you would have two "winning" associations:

• a(1) ,b(1) and c(1): abs(4-8+4) = 0
• a(2), b(2), and c(2): abs(5-13+7) = 1

The possible number of "winning" associations can thus range from 0 up to the length of the shortest vector (3 in this example).

I see how this problem is related to the Hungarian algorithm, but with a cost function that is 3D rather than 2D (which can be solved using the 'matchpairs' function). Or is this more of a shortest path problem? Either way, I'm wondering if there an easy way to solve this.

Answer 1

[Aquatris]

Somthing like this maybe;

a=[ 4  5   2];
b=[-8 -13  3];
c=[ 4  7  -9  11];
thresholdValue = 2;

[A,B,C] = meshgrid(a,b,c);
s = abs(A+B+C); % absolute sum of all combinations of a b c 

idx1 = find(s == min(s,[],'all')); % index for minimum absolute sum
idx2 = find(s < thresholdValue);   % index for absolute sum less than threshold

% winning_1 = [a b c abs(a+b+c)]
winning_1 = [A(idx1) B(idx1) C(idx1) s(idx1)]

winning_1 = 2x4

4 -8 4 0 2 -13 11 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

% winning_2 = [a b c abs(a+b+c)]
winning_2 = [A(idx2) B(idx2) C(idx2) s(idx2)]

winning_2 = 6x4

4 -8 4 0 5 -8 4 1 5 -13 7 1 2 -8 7 1 5 3 -9 1 2 -13 11 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>