2
$\begingroup$

I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!

The problem

Suppose you have nonnegative integer vectors of length d, $x$, $y$, $z \in \mathbb{Z^+}^d$. We know that $\sum_{i=1}^d x_i + y_i = \sum_{i=1}^d z_i$. I wish to find permutation matrices $\Pi_1$ and $\Pi_2$ such that \begin{align} \Pi_1 x + \Pi_2 y = z \end{align}

without enumerating all possible permutations. If there is a solution, I'd like to know in as few steps as possible. If the solution is not unique, I'd like to know all permutation pairs which satisfy the above (or have an efficient means of enumerating them)

More context:

$x$ and $y$ actually represent integer partitions, and I actually have many $x$'s and many $y$'s for any given $z$, and will have to check all possible $x, y$ pairs for the given $z$.

Things I've tried:

  1. We can immediately rule out some $x, y$ pairs using majorization. Let $\tilde{x}$ and $\tilde{y}$ be the sorted versions of $x$ and $y$. I can show that $\tilde{x} + \tilde{y}$ majorizes all other permuted sums of $x$ and $y$. If $z$ majorizes $\tilde{x} + \tilde{y}$ (and is not equal to it, modulo permutation), then it majorizes all permuted sums of $x$ and $y$, so there is no solution. Similarly, $\tilde{x} + \text{reverse}(\tilde{y})$ is majorized by all other permuted sums. If $z$ is majorized by $\tilde{x} + \text{reverse}(\tilde{y})$, then it is majorized by all permuted sums and there is no solution. By partially ordering all the $x$'s using majorization and doing the same for $y$, this method potentially knocks out many pairs without having to check them all.
  2. We can avoid checking all pairs of permutations by using sorting. Let $\tilde{x}$ be the sorted version of $x$ and let $\widetilde{\Pi}_x$ be a permutation which sorts $x$, i.e. $\widetilde{\Pi}_x x = \tilde{x}$. Enumerate all unique permutations of $y$, and subtract them from $z$. Sort each difference vector, and compare it against $\tilde{x}$. Given a match, $\Pi_1$ and $\Pi_2$ can be determined by the permutation of $y$ and the permutation which ``unsorts'' $\tilde{s}$. Formally, suppose for some permutation $\Pi^*$, $s = z - \Pi^* y$ with $\tilde{s} = \tilde{x}$. Then $\Pi_1 = {\widetilde{\Pi}_s}^{-1} \widetilde{\Pi}_x$ and $\Pi_2 = \Pi^*$.
  3. I've found a reduction of the problem to filling in count matrices with specified row, column, and diagonal margins, but haven't found efficient ways of solving that problem. Please chime in if you have thoughts on this. I can say more about this if relevant.

I realize this question is somewhat algorithmic in nature, but I'm hoping there is some relevant area of mathematics that could help. I've tried to think about this from the perspective of symmetric groups, the elementary basis for symmetric functions, general equivalence classes, but I'm not getting very far. Any help or suggested directions would be appreciated!

$\endgroup$
5
  • $\begingroup$ How large is $d$ in practice? How large are the components of $x,y,z$? $\endgroup$
    – D.W.
    Nov 10 '20 at 18:28
  • 1
    $\begingroup$ In Facets of the Three-Index Assigment Polytope by Balas and Saltzman it is shown that a generalized version of your problem is NP-complete. In this generalization we attempt to match arbitrary triplets $(i,j,k)$ with minimal weight $\sum_{ijk} c_{ijk}$ and each $i,j,k$ being used once. Your problem is simply $c_{ijk} = 1- [x_i + y_j = z_k]$ using the Iverson bracket. This means any poly-time solution must explicitly use the substructure given by the addition of vectors, as any strategy that does not is doomed to fail. $\endgroup$
    – orlp
    Nov 10 '20 at 19:28
  • $\begingroup$ D.W. Sorry for the crosspost. I realize this can get out of hand. In this case It seemed potentially interesting/relevant to both communities, and I wasn't getting any traction on the other site. Do you have a recommendation for what to do in this instance. Should I remove the question from the other community before posting here? $\endgroup$ Nov 10 '20 at 20:03
  • $\begingroup$ D.W. $d$ may be very large in practice. Thanks orlp for the link, I'll take a look at this. $\endgroup$ Nov 10 '20 at 20:07
  • $\begingroup$ Yup. You can delete the post on MO if you'd like it to appear here. $\endgroup$
    – D.W.
    Nov 10 '20 at 21:04
3
$\begingroup$

Your problem is equivalent to numerical 3-dimensional matching and is NP-complete.

It is listed under code SP16 in Computers and Intractability; A Guide to the Theory of NP-Completeness by Garey and Johnson.

$\endgroup$
1
  • $\begingroup$ Thanks for the reference. I'll take a look and return to this thread when I've had a chance to think through it. $\endgroup$ Nov 10 '20 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.