The problem that I am looking into feels like something that should have been solved already. However, I cannot find any resource. This could be due to my lack of knowledge of the proper vocabulary. Any suggestion ?
Here's the problem:
We are considering the $N$-uplets of $N$ finite sets $t \in S^*=S_1\times S_2\times\dots\times S_N$. We are also given a positive weight(or score) function $f: S^*\rightarrow\mathbb{R}$. A matching $M \subset S^*$ so that all of its element are disjoint. This means that we cannot have to element $t_1, t_2 \in M$ with the same $s \in S_i$ at position $i$. I am looking for an algorithm to find for M that minimizes (or maximizes) $\sum_{t \in M}f(t)$.
Please note that the matching does not have to cover every element of every set.
If $N=2$, this is basically bipartite weighted graph matching, with plenty of literature. However, if $N>2$, I cannot find any solution. I looked into the more generic case of hypergraph matching, but this is $NP$-complete. My case corresponds to the restricted case where every edge of such hypergraph has exactly one element of each set, which feels restrictive enough to make a simple algorithm (or does it ?).
I am interested in any suggestion or insight, for large N, large cardinality of the sets or both. We can also introduce restrictions on f in necessary.
Thank you in advance.
Though this is more specialized than hypergraph matching, it is still $\mathsf {NP}$-complete: even when $N=3$, and even when the weight function is constant. In that special case, it is exactly the $3$-dimensional matching problem.