I have a number of sets, each containing items with a numerical value and a string.

I want to choose one item out of each set, so that: 1. the strings of the chosen items form a set (i.e. the strings are not equal to any of the strings from the other chosen items) 2. the numerical values of the chosen items are as high as possible

It is not always possible to satisfy 1., e.g. two sets may contain only one item each, both with the same string. When not possible to satisfy 1., the optimal solution is the one that is closest to satisfy 1., 2. is not as important.

How do I find the optimal solution? Are there any widely known algorithms for performing this or something similar?

  • 6
    $\begingroup$ Looks like a maximum weighted bipartite matching problem. $\endgroup$ – Hsien-Chih Chang 張顯之 Jun 28 '11 at 14:40
  • $\begingroup$ @張顯之 : That would be true if the sets were singletons. This looks more complicated. $\endgroup$ – Pat Morin Jun 30 '11 at 17:26
  • $\begingroup$ I think the issue is not entirely clear. If you have two sets A {("WW", 5), ("QQ", 20)} and B {("WW", 3), ("QQ", 19)} What do you think should be solution? If you choose from set А element "QQ", will have to choose from set B "WW", then you will have the greatest value of 20, but the grand total 23. If you choose from set А element "WW", then you have to choose from set B "QQ", then you will have the greatest element 19, but the grand total 24. $\endgroup$ – user5806 Jul 4 '11 at 12:54
  • $\begingroup$ @Pat: To me it looks exactly like max-weight bipartite matching. Left part: sets; right part: strings; there is an edge of weight $w$ between set $S$ and string $x$ if there is pair $(w,x)$ in set $S$. A matching chooses at most one string from each set, and no string is chosen twice. $\endgroup$ – Jukka Suomela Jul 4 '11 at 16:27
  • $\begingroup$ It is not very important in my application. But I would say that a higher grand total is better. $\endgroup$ – Jonatan Kallus Jul 5 '11 at 7:39

Your Answer

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

Browse other questions tagged or ask your own question.