# Maximum-coverage minimum-overlap intersection of sets

I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.

The question I think I need the answer to: given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities? Alternatively, what is the smallest number of cameras I need to have 100% coverage of all points of interest? The latter is the real underlying form of the question, but the former may be an XY problem.

How do I optimize this problem?

My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:

Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could put cameras ("sentries").

Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.

I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.

My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. set([1,3,4])) or a numpy array that's a bitmask of targets viewable (e.g. numpy.array([False,True,False,True,True],dtype=bool)), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).

I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.

My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will always be preferred.

• Without knowing more about the restrictions to your problem, it sounds an awful lot like the Set cover problem which is NP-hard. Feb 1, 2021 at 15:58
• Yes! That is exactly it! And of course it's NP-hard... But at least this has given me a place to start; thank you! Feb 1, 2021 at 16:26
• @PålGD post your comment as an answer and I’ll accept it (because it indeed the exact right answer) Feb 3, 2021 at 3:59