# Solving the "reverse" Assignment Problem?

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|$$.

• If you have a polynomial time algorithm that computes the sum $\Sigma_{a \in A} C(a, f(a))$ for any given sets $A$ and $T$, and any given bijection $f: A \to T$, then can't you just, for all $a\in A$ and $b\in T$, feed it the sets $A' = \{a\}, T' = \{b\}$, and the bijection $f': A' \to T'$ that is given by $f'(a) = b$? Commented Aug 10 at 17:51
• Also, it is not clear how this is a reverse problem as it does not optimize any function, as opposed to the original problem. I think the question is not clear enough. Commented Aug 10 at 17:53
• @BaderAbuRadi 1. Well $C$ is defined for only $A$ and $T$ --- I don't think I said it was defined for arbitrary sets. 2. Well, that's why I said it was similar, as there are some elements that are different. Commented Aug 10 at 20:54
• We generally ask that you avoid changing the question in a way that invalidates existing answers. Instead, please take to make sure you are asking the question you want answered from the start. If you discover you have a follow-up question or should have asked a different question, you can ask a new question using the 'Ask Question' button. Also, please don't use "Update: ...". See cs.meta.stackexchange.com/q/657/755
– D.W.
Commented Aug 10 at 23:55
• By the way, the reasoning for this is that it avoids confusion (e.g., where there are multiple answers that each address different versions of the question), and we want to build an archive of knowledge that will be useful to others in the future, so we want to keep it clean and tidy to make it useful for others. Thank you!
– D.W.
Commented Aug 10 at 23:57

(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!)$$.

• @BaderAbuRadi It proves that (in the continuous case) there are multiple indistinguishable (or no) solutions. So an algorithm can find one such solution, or show that no such solution exists. But finding a solution if it exists is easy to do in polynomial time, since we only have $n^2$ variables - so just choose $(n-1)^2+1$ equations whose coefficient vectors are linearly independent and compute a solution. That's then $\mathcal O(n^6)$. You can do this as well if you don't know whether a solution exists, but then you have to check whether your solution holds up for all $n!$ equations... Commented Aug 11 at 20:06
• There are examples where there is at least one solution but the algorithm cannot find the required C. Note that C is fixed but hidden and we want to find the hidden fixed C, not a different C' that works, unless I miss something in the question's definition. Since A, T and the hidden C are all fixed, there is always a solution -- so the no solution possibility is not relevant. The question is can we find the specific hidden C and not decide if there is some C' that works or find some C' that is possibly different than the hidden one. Commented Aug 11 at 20:16
• @BaderAbuRadi There is no need to give an example, since I've shown that the solutions are indistinguishable - thus there can not exist an algorithm that picks the right solution from the many possible solutions. What your example does though, is extend my statement to $n=2$ for the binary case. Note conversely, that your statement in turn only shows that there can not be an algorithm for all $n$. It might still be possible for $n\ge 3$ (since the number of equations rises faster than the number of variables, I don't see it as trivial that for $n\ge 3$ there is still no algorithm) Commented Aug 11 at 20:22
• So I would just suggest to edit your answer by adding a note that emphasizes that in the continuous case, as infinitly many solutions exist, then no algorithm have enough information to point at the hidden C. Anyway it easy to find an example already in the non-continuous case, yet your solution ia confusing in the sense that the reader may think that you are trying to find some C' and not trying to refute the existence of an algorithm. Commented Aug 11 at 20:27

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.

• I wonder what would happen if you make it so that for a given $a$, there is exactly one $y \in T$ where $C(a,y)=1$, and similarly, for a given value of $b$, there is exactly one value of $x \in A$ there $C(x,b)=1$. This will probably help to remove the chances of multiple solutions. Commented Aug 10 at 22:21
• Once you map $1$ to a letter in $\{ x, y\}$, then there is one way to complete this to a bijection by mapping $2$ to the other letter. So there are only two bijections, one that maps $1$ to $x$, and the other that maps $1$ to $y$. Regarding your first comment, that would be a different question. What is the motivation behind the problem you presented? We prefer to ask a single question per post in this site. Commented Aug 10 at 22:31
• 1. Yeah, I noticed that, so I deleted the comment. 2. This is an attempt at solving the formalization of a problem where you are trying to line a group of objects in a pre-determined sequence, but you are only told how many objects are in the correct locations (it's like Wordle, but if all squares are either yellow or green, and you only know how many squares are green, but not which squares are green). Commented Aug 10 at 22:33
• @DarkRise it's closer to Mastermind game, without the white pegs. Commented Aug 11 at 5:39