Is there an algorithm for constructing sets A and B whose combined size is minimum, given a particular subset of all the possible unordered pairs of elements, one from A and one from B?

Example: Sets A and B contain musical notes as their elements. Given a particular set of two-note chords that must be produced, how shall I construct A and B such that the combined number of notes in A and B is smallest?

Can the algorithm (if there is one) be extended to constructing more than two sets with unordered tuples?

  • $\begingroup$ I believe this is NP-hard. However, I would approach this by converting this into a graph, and analyzing the adjacency matrix. $\endgroup$ – Don Thousand Aug 21 '18 at 20:32
  • $\begingroup$ Can you explain your question a little bit more? or maybe give a concrete example? $\endgroup$ – Quimey Aug 21 '18 at 20:58

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.