Max Covering

327. Max Covering

Max Covering Location Problem (MCLP): place exactly $𝑝$ facilities to maximize the demand covered. Inversion of set covering: fix count, maximize coverage.

327.1. Formulation

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

Decision variables:

$𝑦_{𝑗}$ = open facility $𝑗$ ?
$𝑧_{𝑖}$ = customer $𝑖$ covered? (auxiliary)

max \sum_{𝑖} 𝑑_{𝑖} 𝑧_{𝑖}

s.t.:

𝑧_{𝑖} \leq \sum_{𝑗 \in 𝑁_{𝑖}} 𝑦_{𝑗}, \forall 𝑖 (i covered only if at least one nearby facility is open)

\sum_{𝑗} 𝑦_{𝑗} = 𝑝

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

327.2. Picture

With $𝑝 = 2$ facilities and a fixed coverage radius, a low-demand outlier (red) is left uncovered — the budget is spent capturing the most demand.

327.3. Connection to $𝑝$ -center and set covering

Problem	Objective	Fixed
Set covering	minimize number of facilities	cover all demand within $𝑑_{max}$
$𝑝$ -center	min $𝑑_{max}$	$𝑝$ facilities, cover all
Max covering	max demand covered	$𝑝$ facilities and $𝑑_{max}$ fixed

Picks two corners (fix $𝑝$ and $𝑑_{max}$ ) and maximizes coverage. Useful when budget and service distance are both constraints.

327.4. Greedy approximation

Greedy is a $1 - \frac{1}{𝑒} \approx 0.63$ approximation:

While p facilities not yet picked:
    Pick the facility that adds the most new covered demand

This is optimal for max-coverage problems (Nemhauser-Wolsey-Fisher 1978) — no polynomial-time algorithm exceeds $1 - \frac{1}{𝑒}$ unless P = NP.

327.5. Submodularity

The function $𝑓 (𝑆) =$ “demand covered by set of facilities $𝑆$ ” is monotone submodular:

𝑓 (𝑆 \cup {𝑗}) - 𝑓 (𝑆) \geq 𝑓 (𝑇 \cup {𝑗}) - 𝑓 (𝑇) for 𝑆 \subset 𝑇

— adding $𝑗$ to a smaller set gives at least as much marginal value as adding it to a bigger set (diminishing returns).

The $1 - \frac{1}{𝑒}$ bound is the classical Nemhauser bound for monotone submodular maximization with a cardinality constraint.

327.6. Applications

Retail — pick $𝑝$ store locations to capture max market share within an acceptable drive time
Cell towers — $𝑝$ towers to cover the most population
Recall logistics — pick $𝑝$ warehouses to recall product from
Influence maximization — viral marketing, $𝑝$ seed users to maximize reach