Set Covering

326. 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 $𝑑_{max}$ of some facility.

326.1. Formulation

Let $𝑁_{𝑖} = {𝑗 : 𝑐_{𝑖 𝑗} \leq 𝑑_{max}}$ — candidate facilities that can cover customer $𝑖$ .

min \sum_{𝑗} 𝑦_{𝑗}

s.t.:

\sum_{𝑗 \in 𝑁_{𝑖}} 𝑦_{𝑗} \geq 1, \forall 𝑖 (each customer covered by ≥ 1 facility)

𝑦_{𝑗} \in {0, 1}

326.2. Picture

Each facility covers a disc of radius $𝑑_{max}$ ; every customer must fall inside at least one open disc.

326.3. 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.

326.4. 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 $𝐻_{𝑛} \approx ln 𝑛$ is the harmonic sum). And this is optimal — no polynomial algorithm achieves better than $(1 - 𝑜 (1)) ln 𝑛$ unless P = NP.

326.5. Linear programming relaxation

Drop $𝑦_{𝑗} \in {0, 1}$ to $𝑦_{𝑗} \in [0, 1]$ . 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 $𝑂 (log 𝑛)$ -factor approximation

326.6. Variants

Weighted set cover: each facility $𝑗$ has cost $𝑤_{𝑗}$ . Minimize $\sum_{𝑗} 𝑤_{𝑗} 𝑦_{𝑗}$
Maximum coverage (here): inverted — fix facility count $𝑝$ , maximize coverage
Partial cover: cover at least $𝑘$ of $𝑛$ customers

326.7. Where it shows up

Fire / EMS placement — every household within $𝑑_{max}$ 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

326.8. See also

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