Identifying a starting point for maximum coverage

Question

I have 10,000 sequentially numbered items I wish to characterize. For each item, I created a list of the other items I think might have a similar characteristic.

i.e.

Item 1: [2,4,7,8,9,...,9489] (list contains 250 items)
Item 2: [1,4,13,23,...,9424] (list contains 12 items)
Item 3: [1,2,4,7,...,9489] (list contains 140 items)
Item 4: [1,3,7,9,...,9211] (list contains 250 items)
Item 5: [1,3,7,9,...,9221] (list contains 250 items)
Item 6: [1,2,7,25,...,9248] (list contains 241 items)
Item 7: [4,5,6] (list contains 3 items)

If I only have time to test 50 items, How might I choose which items to test so that the maximum number of items is represented? The identified similarity is not necessarily bi-directional - notice item 7's list contains 4,5,6 but not 1 and 3(which both have 7 in their list).

Some lists may be very similar or even identical, as seen in items 4 and 5. Testing both 4 and 5 would not achieve the maximum coverage.

Answer 1

It sounds like you want to select a set of 50 lists whose union contains as many elements as possible. This is the maximum coverage problem, which is NP-complete, but there are standard techniques that can be used to get decent-quality solutions (there is an approximation algorithm using a greedy algorithm, and a formulation as ILP).