324. Max Covering

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

324.1. Formulation

Let = demand at customer . Let — facilities that can cover .

Decision variables:

• = open facility ?
• = customer covered? (auxiliary)

s.t.:

324.2. Connection to -center and set covering

Picks two corners (fix and ) and maximizes coverage. Useful when budget and service distance are both constraints.

324.3. Greedy approximation

Greedy is a 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 unless P = NP.

324.4. Submodularity

The function “demand covered by set of facilities “ is monotone submodular:

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

The bound is the classical Nemhauser bound for monotone submodular maximization with a cardinality constraint.

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

324.6. See also

• Set Covering — dual variant
• -center
• Facility Location overview