Assignment problem cost matrix reconstruction justification

Question

I have asked questions numerically on this topic, but here is a theoretical question that i want to ask, if the answer is affirmative, then only can i proceed with my problem. I have an assignment problem whose solution I have, i.e. I know the job assignments been done, and I know the minimum cost of the entire problem. My question is can I get the cost matrix from these two information, or can i get some approximation of the cost matrix. Please refer to question Finding integer solutions to a multivariable equation.

Answer 1

No. Consider a 2x2 assignment problem (two workers, two jobs), and let $C$ be the 2x2 cost matrix. Assume that the optimal solution assigns worker 1 to job 1 and worker 2 to job 2, at total cost $z$. That tells you the following two things:\begin{align*} C_{11}+C_{22} & =z\\ C_{11}+C_{22} & \le C_{12}+C_{21}. \end{align*} Conversely, that information is sufficient to dictate the solution you have. Even if you assume $C\ge 0$, you have an uncountably infinite number of solutions to that system, all of which are consistent with what you know.