Let there be $n$ set of ordered pairs
$s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$,
$s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$,
$s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$,
$s_n=\{(c_n,f_1)(c_n,f_2) ...(c_n,f_m)\}$


$T((c,f))$ be a function that takes an ordered pair or element of the sets and returns a positive rational number.

can we select one element each from all the $n$ sets such that $\sum T((c_i,f_j)) =T$ where $\bigcap_{i=1}^{n } c_i =\phi$

  • $\begingroup$ I think that the question tries to be that we need to select a transversal, i.e., at most one element from each column. Am I right? $\endgroup$ – domotorp Jul 16 '19 at 16:31
  • $\begingroup$ @domotorp yes that would be one way to put it $\endgroup$ – AVIK DUTTA Jul 16 '19 at 16:35
  • $\begingroup$ Well, I really don't think this question belongs here, it does look too easy. $\endgroup$ – domotorp Jul 16 '19 at 19:57

This problem is in NP. (easy to verify a given solution)

Subset sum is NP-Complete, so this problem can be reduced to subset sum.

  • $\begingroup$ Can we really say that there will be a solution =T ? $\endgroup$ – AVIK DUTTA Jul 17 '19 at 17:43

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.