A constructive proof of Swap Local Search worst-case instances for the Maximum Coverage Problem

Journal article (2016)

Authors

R.B.O. Kerkkamp Erasmus Universiteit Rotterdam
K. Aardal Discrete Mathematics and Optimization - EEMCS , Centrum Wiskunde & Informatica (CWI)
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

We consider the Maximum Weighted Coverage problem (MCP). We can relate the MCP to optimisation problems using submodular functions. Performance guarantees of the Swap Local Search algorithm are known for these problems, but can be improved for the MCP. Our main contribution is a constructive proof of tight performance guarantees for Swap Local Search applied to the MCP, which provides insight into the structure of worst-case MCP instances, and has the potential to be applicable to other optimisation problems.