The Swap Locality Gap for the Maximum Covering Location Problem

In the Maximum Covering Location problem (MCLP) we have to decide a fixed and finite number of base locations such that the resulting base coverage is maximised. Although the underlying assumptions of this simplistic model are restrictive, it is often used to quickly obtain preliminary results or as a subroutine of more complex algorithms. For example, it is used in Emergency Medical Service optimisation models.

The MCLP is NP-hard, but can be solved reasonably well. One of the basic heuristics for the MCLP is the Swap Local Search. We give a new proof of the tight performance guarantee for the Swap Local Search applied to the MCLP. It is a constructive proof of the worst-case MCLP instances, which turn out to have a certain symmetry. Furthermore, the story of finding the proof is an example of how numerical results can be used to construct mathematical proofs.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars