323. Set Covering

Set Covering Location Problem (LSCP): minimize the number of facilities needed to cover every customer at least once. “Cover” = customer is within an acceptable distance of some facility.

323.1. Formulation

Let — candidate facilities that can cover customer .

s.t.:

323.2. The general Set Cover problem

LSCP is a special case of Set Cover: given a collection of subsets covering a universe, find the minimum number to use.

Set Cover is one of Karp’s 21 NP-complete problems — a foundational hard problem in complexity theory.

323.3. Greedy approximation

The natural greedy algorithm:

At each step: pick the facility that covers the most uncovered customers
Stop when all customers are covered

Achieves an -approximation (where is the harmonic sum). And this is optimal — no polynomial algorithm achieves better than unless P = NP.

323.4. Linear programming relaxation

Drop to . Solve the LP:

• LP gives a lower bound on integer optimum
• LP value can be a fractional cover (some partially selected)
• Randomized rounding converts LP solution to integer solution with -factor approximation

323.5. Variants

• Weighted set cover: each facility has cost . Minimize
• Maximum coverage (here): inverted — fix facility count , maximize coverage
• Partial cover: cover at least of customers

323.6. Where it shows up

• Fire / EMS placement — every household within minutes
• Cell tower placement — every demand area covered
• Sensor placement — every region monitored
• Scheduling / shift staffing — every hour staffed (set-cover on time intervals)
• Vaccine distribution — every village within reach

323.7. See also

• Max Covering — inverted variant
• -center — uses set covering as feasibility subroutine
• Facility Location overview