2
$\begingroup$

I've written a political quiz based on data from the public whip. They group politicians' votes by policy; each vote can belong to many policies. There are too many policies for me to ask a question for each one, and anyway some are duplicates and some policies' votes are subsets of other policies. In the past, I've manually chosen a subset of policies to use in my quiz try to maximise the number of votes included without double-counting any, but I'm worried that that may introduce my biases into what is supposed to be as neutral as possible a quiz. So I'd like to find the set of policies which maximises the number of votes included without counting any of them twice.

Is there a known algorithm I could use to do this? I've seen similar questions elsewhere on this site but they generally seem to involve sets of intervals or geometric shapes.

$\endgroup$
  • 2
    $\begingroup$ Your problem is NP-hard, by reduction from independent set (represent each vertex by the set of edges incident to it). You can try the greedy heuristic. $\endgroup$ – Yuval Filmus Jan 2 '18 at 12:44
3
$\begingroup$

The problem you describe is known as set packing, and it has a natural ILP formulation. You can start with some ILP solver you have access to, and it should be a highly competitive solution. There are many heuristics to choose from as well if you don't require optimal solutions.

$\endgroup$

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.