Given a list of sets:

a b c -> _
c d   -> d
b d   -> b
a c   -> a
a c   -> c

The objective is to find the max partition of unique elements with each element corresponding to the set containing that element.

I was thinking about ordering the elements in n * log(n) based on occurrence in other groups and then iteratively start with the lowest, and reorder the list each time based on subtracting the occurrences of other elements within the lists containing the removed element. We are able to do so, as each unique element contains a set of pointers to the lists where the element is contained in.

I can store the unique elements with its occurrences in a Min-Heap, where each unique element has handler to the node within the Min-Heap, thus we can remove the min and also decrease the key one for others within the same list as the contained element in log(n) giving that we have it's handler.

Is the approach feasible at all, if not, what approach I can make use of?

  • $\begingroup$ If I understand correctly, this problem is just maximum bipartite matching, which can be done in $\mathcal{O}(E \sqrt{V})$ time with the Edmonds-Karp algorithm. It is likely that your greedy algorithm does not always produce an optimal solution. $\endgroup$ – Antti Röyskö Jan 19 '20 at 11:35
  • $\begingroup$ @AnttiRöyskö Yeah, I haven't thought about looking at it as a graph and just search for the max-flow, thanks for pointing that out. $\endgroup$ – DomainFlag Jan 19 '20 at 13:04

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.