Solving the "reverse" Assignment Problem?

Question

According to Wikipedia, the assignment problem can be formally defined as:

Given two sets, A and T, together with a weight function $C : A \times T \to R$. Find a bijection $f : A \to T$ such that the cost function:

$\sum_{a \in A} C(a, f(a))$

is minimized.

I now have a problem that is similar to a "reverse" of this problem --- let's say that for a given bijection $f$, we can compute in polynomial time $\sum_{a \in A} C(a, f(a))$; however, we do not know $C(a, f(a))$ for any single element $a \in A$.

Is there an algorithm that can find $C(a, b)$ for $a \in A$, and $b \in T$ for any $a$ and $b$ in polynomial time? If it makes it easier, we also know that in this case, $C \in \{0,\, 1\}$. You can also assume that $|A|=|T|$.

Answer 1

(Edited after comment-discussion)

The following answer shows that in the continuous case, there exist either no, or infinitely many possible solutions for $C$.

Let $|S|=|T|=n$. Rename the elements of $S $ and $T$ to be $1,...,n$. Then our equations are

$$ \forall \sigma\in S_{n}:\quad \sum_{i=1}^{n} \underbrace{C(i,\sigma(i))}_{:=x_{i,\sigma(i)}}= c_\sigma $$

, and $x_{i,j}$ are our unknowns.

Let further $P_\sigma$ be the permutation matrix corresponding to $\sigma$. Then we have that $$ \sum_{i=1}^{n} x_{i,\sigma(i)} =((P_\sigma)_1,...,(P_\sigma)_n)\pmatrix{(x_{1,i})_{i\in[n]}\\\vdots\\ (x_{n,i})_{i\in[n]}} $$ , where $(P_\sigma)_j$ denotes the $j$-th row of $P_\sigma$ (as a row vector), and $(x_{j,i})_{i\in[n]}$ denote column vectors for all $j\in[n]$.

With this we arrive at the linear equation system $$ \forall \sigma\in S_{n}:\quad ((P_\sigma)_1,...,(P_\sigma)_n)\pmatrix{(x_{1,i})_{i\in[n]}\\\vdots\\ (x_{n,i})_{i\in[n]}} = c_\sigma\tag{1} $$

Since we have $n^2$ variables, but the dimension of the space spanned by all permutation matrices only has dimension $(n-1)^2+1$, we arrive at the conclusion that the equation system is underdetermined, so it either has no solutions, or infinitely many (depending on the $c_\sigma$).

So, if our goal is to find a certain solution $C$, then there can't exist such an algorithm.

If we know that there exists a solution $C$, and our goal is merely to find one such $C$, then it suffices to pick $(n-1)^2+1$ linearly independent equations from (1) as a linear equation system, and compute a solution for it. Since we have $n^2$ variables and $(n-1)^2+1$ equations, finding such a solution can be done in time $\mathcal O(n^6)$.

If we don't know whether there exists a solution $C$, the above method still yields a candidate for a solution. But in this case, we'll need to check if a solution exists. This is the case if and only if our solution candidate satisfies all equations in (1), and checking this takes time $\Omega(n!)$.

Answer 2

I don't think such an algorithm exists, regardless of its complexity. Consider for example the sets $A = \{ 1, 2\}$ and $T = \{ x, y\}$. Assume that $C(a, b)\in \{0, 1 \}$ for all $(a, b)\in A\times T$. Assume also that:

• $C(1, x) = C(2, x) = 1$.
• $C(1, y) = C(2, y) = 0$.

There are two possible bijections form $A$ to $T$, one that maps $1$ to $x$ (denote it by $f_x$), and the other maps $1$ to $y$ (denote it by $f_y$).

It is not hard to see that $\sum\limits_{a\in A} C(a, f_x(a)) = \sum\limits_{a\in A} C(a, f_y(a)) = 1$. So from all possible bijections, you can conclude that the sum is always one, however, that does not give you any information on the underlying values of $C(a, b)$ for any $(a, b)\in A\times T$. For example, if I modify the underlying values to:

• $C(1, x) = C(2, x) = 0$.
• $C(1, y) = C(2, y) = 1$.

You would still get that both bijections give you sum 1 each. In other words, different underlying values can induce the same sums, and so you do not have enough information to compute $C(a, b)$ based only on the sums.