Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fixed size set to contain the maximum number of given sets

Tags:

algorithm

set

I have about 1000 sets of size <=5 containing numbers 1 to 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... 

Is it possible to find a set of size 20 that contains the maximum number of given sets?

Checking each of 100!/(80!*20!) sets, is inefficient.

like image 271
albert Avatar asked Jun 08 '14 09:06

albert


1 Answers

I am not so sure this is NP complete.

Consider the related problem where we get a reward of x for each set, but have to pay a price of y for each number that we want to allow. (A set only pays the reward if all the numbers it contains have been paid for.)

You can solve this type of problem using the max flow algorithm by:

  1. Setting up a source node
  2. Setting up a destination node
  3. Setting up a node for each set
  4. Setting up a node for each number
  5. Add edge from source to each set with capacity x
  6. Add edge from each number to dest with capacity y
  7. For each number a in set s, add edge from s to a with infinite capacity

Solving the maximum flow problem on this graph (from the source to destination node) finds a minimum cut cost c.

The net amount of money we would make would be N.x-c (where N is the number of sets).

If we can choose y (e.g. by bisection) such that we have selected exactly 20 numbers, then we have managed to solve for the maximum number of sets with 20 numbers.

like image 92
Peter de Rivaz Avatar answered Oct 09 '22 06:10

Peter de Rivaz